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

💡백트래킹은 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 {
    public List<List<Integer>> permute(int[] nums) {
        // 답변 리스트 초기화
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(new ArrayList<>(), new boolean[nums.length], nums, ans);
        return ans;
    }

    private static void backtrack(List<Integer> curr, boolean[] visited, int[] nums, List<List<Integer>> ans) {
        // base condition
        if (curr.size() == nums.length) {
            // curr의 모든 원소를 복사해서 새로운 ArrayList를 생성
            ans.add(new ArrayList<>(curr));
            return;
        }

        // 후보군 탐색
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                // 후보군 선택(상태 변화)
                visited[i] = true;
                curr.add(nums[i]);

                // 재귀 호출(Depth 증가)
                backtrack(curr, visited, nums, ans);

                // 상태 원상 복구
                visited[i] = false;
                curr.removeLast();

            }
        }
    }

}

• 🚨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 {
    public List<List<Integer>> combine(int[] nums, int r) {
        // 답변 리스트 초기화
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(new ArrayList<>(), new boolean[nums.length], nums, ans, 0, 2);
        return ans;
    }

    private static void backtrack(List<Integer> curr, boolean[] visited, int[] nums, List<List<Integer>> ans, int start, int r) {
        // base condition
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        // 후보군 탐색
        for (int i = start; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                curr.add(nums[i]);

                backtrack(curr, visited, nums, ans, i + 1, r);
                visited[i] = false;
                curr.removeLast();
                
            }
        }
    }
}

• 💡순열의 후보군 탐색 로직에서는 backtrack()을 호출하면 다시 처음 인덱스부터 순회하고 visited로 상태 변화를 체크하지만, 조합에서는 원소를 선택만 하면 되기 때문에 backtrack을 호출할 때마다 시작 인덱스를 i + 1로 증가시켜야 한다.

💻부분집합 코드

public class Subset {
    public List<List<Integer>> subset(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // 0~n까지의 모든 조합을 구함
        for (int r = 0; r < nums.length + 1; r++) {
            backtrack(nums, new ArrayList<>(), ans, new boolean[nums.length], 0, r);
        }

        return ans;
    }

    private static void backtrack(int[] nums, List<Integer> curr, List<List<Integer>> ans, boolean[] visited, int start, int r) {
        // base condition
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        // 후보군 탐색
        for (int i = start; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                curr.add(nums[i]);
                backtrack(nums, curr, ans, visited, i + 1, r);
                visited[i] = false;
                curr.removeLast();
            }
        }
    }
}

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

⏰시간복잡도

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

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