간단한 백트래킹 + 구현 문제

문제는 다음과 같다.

String 이 주어진다.
해당 String을 구성하는 알파벳 전부를 사용해서, 또다른 String을 만들어라.
만들어낸 String이 문자 두개 이상 중복되면 제외해라.
만들어낸 String들을, 사전순 정렬하고 return해라.

입력 예시
String abbc

출력 예시
{abcb, abcb, babc, bacb, bcab, bcba, babc, bacb, bcab, bcba, cbab, cbab}

풀이는 다음과 같다.

이렇게 보면 어려운 문제가 아니다.
문제 풀때도 어.. 백트래킹 하고..
라고 생각했는데,
백트래킹 하면서 중복 문자를 포함하는 친구들을 제외하려고 생각하니까
너무 꼬여버렸다.

그래서 그냥,
백트래킹으로 모든 문자열을 만들어낸 후
문자열을 배열에 저장하고,

해당 문자열 배열을 순회하며 중복되는 친구들을 없에며 출력해줬다.

코드는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<String> answer = new ArrayList<>();
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String s1 = "abbc";
        char[] a = s1.toCharArray();
        Arrays.sort(a);
        visited = new boolean[4];

        backTracking(a, "", 0);
        ArrayList<String> arr = new ArrayList<>();
        for(String s : answer) {
            if(check(s)) arr.add(s);
        }

        //Collections.sort(arr);

        for(String s : arr) {
            System.out.println(s);
        }


    }

    static void backTracking (char[] arr, String word, int depth) {
        if(depth == 4) {
            answer.add(word);
            return;
        }

        for(int i = 0 ; i < 4 ; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            word += arr[i];
            backTracking(arr, word, depth+1);
            if(word.length() == 1) {
                word = "";
            }
            else {
                word = word.substring(0, word.length()-1);
            }
            visited[i] = false;
        }
    }

    static boolean check(String s) {
        for(int i = 0 ; i+1 < s.length() ; i++) {
            if(s.charAt(i) == s.charAt(i+1)) return false;
        }
        return true;
    }

}

아쉽다..
어려운 문제가 아닌데 헤매서.. ㅠㅠ