[코딩테스트] Java - 재귀/백트래킹

 

🔹 예시 1. 1부터 N까지 수 중에서 중복 없이 R개 고르기 (순열)

public class BacktrackingExample {
    static int N = 4, R = 2;
    static int[] arr = {1, 2, 3, 4};
    static boolean[] visited = new boolean[N];
    static int[] output = new int[R];

    public static void main(String[] args) {
        dfs(0);
    }

    static void dfs(int depth) {
        if (depth == R) {
            System.out.println(Arrays.toString(output));
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];

                dfs(depth + 1);  // 다음 위치로

                visited[i] = false;  // 백트래킹
            }
        }
    }
}

🔍 백트래킹 포인트:
visited[i] = false로 되돌리면서 다음 시도를 계속하는 것!
→ 이게 없으면 모든 재귀 경로에서 방문 상태가 유지돼서 잘못된 결과가 나와.

---

🔹 예시 2. 1부터 N까지 더해서 S가 되는 모든 수열 구하기

public class SubsetSum {
    static int N = 4;
    static int S = 5;
    static int[] arr = {1, 2, 3, 4};

    public static void main(String[] args) {
        dfs(0, 0, "");
    }

    static void dfs(int idx, int sum, String path) {
        if (sum == S) {
            System.out.println(path);
            return;
        }

        if (idx >= N || sum > S) return;  // 가지치기

        // 포함
        dfs(idx + 1, sum + arr[idx], path + arr[idx] + " ");
        // 미포함
        dfs(idx + 1, sum, path);
    }
}

🔍 백트래킹 핵심:

• sum > S 이면 더 이상 진행 불가 → pruning (가지치기)
• path는 결과 수열 저장용

---

🔹 예시 3. 괄호 문자열 만들기 (백트래킹 + 조건)

public class GenerateParentheses {
    static int N = 3;  // 괄호 쌍의 수

    public static void main(String[] args) {
        generate("", 0, 0);
    }

    static void generate(String s, int open, int close) {
        if (s.length() == N * 2) {
            System.out.println(s);
            return;
        }

        if (open < N) generate(s + "(", open + 1, close);
        if (close < open) generate(s + ")", open, close + 1);
    }
}

🔍 조건:

• (는 N개까지 가능
• )는 (보다 많이 쓰이면 안 됨 → 이게 백트래킹 조건!

---

📌 정리: 백트래킹의 핵심

포인트 설명

종료 조건	depth, sum 등으로 탈출
방문 체크	visited 배열로 중복 방지
백트래킹	재귀 호출 후 상태 복구 (visited = false 등)
가지치기	sum > 목표값 등으로 무의미한 경로 제거