📢이 포스트는 백트래킹의 대표적인 예시인 순열, 조합, 부분집합을 자바 코드로 구현을 하기 위한 글이기 때문에 자세한 내용이 궁금하시면 완전탐색(파이썬 버전)을 참고하시면 됩니다.

💡백트래킹은 State Tree(DFS) 자료구조를 기반으로 동작하는 재귀함수 알고리즘이기 때문에, base condition과 후보군을 탐색하기 위한 코드 2가지로 나뉠 수가 있다.

💻따라서 백트래킹 공통 템플릿은 다음과 같다.

void backtrack(현재상태, 기타파라미터) {
    // 1. Base condition (문제별로 다름)
    if (종료조건) {
        결과저장();
        return;
    }
    
    // 2. 후보 탐색 (문제별로 다름)
    for (후보들) {
        if (유효한후보) {
            // 선택
            상태변화();
            
            // 재귀 호출
            backtrack(다음상태);
            
            // 백트래킹 (항상 동일)
            상태복구();
        }
    }
}

위의 공통 템플릿이 순열, 조합, 부분집합에 적용될 때 어떻게 달라지는지 심도있게 살펴보자.

📢코드 최적화를 수행했으니, 아래의 코드들은 위의 공통 템플릿과 다를 수가 있습니다.

순열

ex) nums=[1, 2, 3, 4]로 만들 수 있는 모든 순열을 리턴하라.

💡curr와 ans는 리스트로 초기화한다.
⚙️스토리는 다음과 같다:

1. base condition: if len(curr) ==len(nums)가 참이면 순열로 만들 수 있으므로 ans에 삽입하고, 리턴문으로 재귀 함수를 호출한 곳으로 돌아가게 한다.

2. for문으로 후보군을 탐색한다.
   2.1. State Tree에 후보가 없으면 -> curr에 후보를 삽입하고 재귀 함수를 호출해서 Depth 증가시킴
   2.2. 호출한 곳으로 돌아감으로써 Depth를 감소시키고, curr에 후보를 제거한다.
   2.3. State Tree에 후보가 있으면 -> 그대로 for문을 순회시켜서 2.1 과정을 스킵한다.

3. ans를 리턴

💻순열 코드

public class Permutation {
    // 1. 순열
    public static List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        boolean[] visited = new boolean[arr.length];

        permuteHelper(arr, curr, ans, visited);
        return ans;
    }

    private static void permuteHelper(int[] arr, List<Integer> curr, List<List<Integer>> ans, boolean[] visited) {
        // base condition
        if (curr.size() == arr.length) {
            ans.add(new ArrayList<>(curr)); // 깊은 복사(즉, curr의 원소들을 삽입한다)
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true; // 먼저 방문을 하고
                curr.add(arr[i]); // 상태 노드를 추가
                permuteHelper(arr, curr, ans, visited);
                curr.remove(curr.size() - 1); // 상태 노드를 제거하고
                visited[i] = false; // 방문을 해제
            }
        }
    }
}

• 🚨ans.add(curr)로 하면 후보군 탐색 로직 curr도 같은 객체를 공유하기 때문에 변경된 값에 영향을 받는다.
  • 🔖값을 깊게 복사하지 않기 때문에 이것을 Shallow Reference(or copy)라고 한다.
• 후보군 탐색 순회에서 for (int i : nums)는 value만을 순회하기 때문에 visited에서 인덱싱을 사용할 수 없다.
• backtrack에서의 actual parameter와 formal parameter를 넣어줄 때도 마치 List<Integer> curr = new ArrayList<>();로 참조하는 것처럼 작성해주면 된다.

💻조합 코드

public class Combination {
    // 2. 조합
    public static List<List<Integer>> combine(int[] arr, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();

        combineHelper(arr, curr, ans, k, 0);
        return ans;
    }

    private static void combineHelper(int[] arr, List<Integer> curr, List<List<Integer>> ans, int k, int start) {
        // base condition
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        for (int i = start; i < arr.length; i++) {
                curr.add(arr[i]);
                combineHelper(arr, curr, ans, k, i + 1); // 내 오른쪽만 재귀적으로 탐색
                curr.remove(curr.size() - 1);
        }
    }
}

• 💡순열의 후보군 탐색 로직에서는 backtrack()을 호출하면 다시 처음 인덱스부터 순회하고 visited로 상태 변화를 체크하지만, 조합에서는 원소를 선택만 하면 되기 때문에 backtrack을 호출할 때마다 시작 인덱스를 i + 1로 증가시켜야 한다.
• 어짜피 오른쪽 놈부터 재귀적으로 탐색을 하기 때문에 굳이 if (!curr.contains(arr[i]))로 상태를 검증할 필요가 없다.

💻부분집합 코드

public class Subset {
    // 3. 부분집합
    public static List<List<Integer>> subset(int[] arr) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();

        for (int k = 0; k < arr.length + 1; k++) {
            subsetHelper(arr, curr, ans, k, 0);
        }

        return ans;
    }

    private static void subsetHelper(int[] arr, List<Integer> curr, List<List<Integer>> ans, int k, int start) {
        // base condition
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        for (int i = start; i < arr.length; i++) {
                curr.add(arr[i]);
                combineHelper(arr, curr, ans, k, i + 1); // 내 오른쪽만 재귀적으로 탐색
                curr.remove(curr.size() - 1);
        }
    }
}

• 부분집합 함수는 조합 템플릿 함수에서 nums의 길이만큼 순회하면서 backtrack을 호출하면 된다.
  • 이때, 순회하면서 증가하는 k을 backtrack의 인자로 보내줘야 k을 base condition에서 체크함으로써 ans에 추가시킬 수 있다.
    • 즉, 인자의 고정값인 k를 가변적으로 변화시켰다고 보면 된다.

⏰시간복잡도

순열: $O(n! * n)$
조합: $O(C(n, r) * r)$
부분집합: $O(C(n, r) * n)$

• 💡옆에 숫자가 곱해진 이유는 new ArrayList<>(curr)로 복사하는 시간이 추가로 필요하기 때문이다.
  • 🔎좌항을 기본 시간복잡도라고 보면 된다.