백트래킹(기본, 순열, 조합, 부분집합)

기본

import java.util.*;
 
public class Main {
 
    static int N;                 // 원소 개수 (예: 배열 길이, 숫자 개수)
    static int[] arr;             // 사용할 원소들
    static boolean[] visited;     // 방문 여부 체크
    static List<Integer> path;    // 현재까지 선택한 원소 (백트래킹 경로)
 
    public static void main(String[] args) {
        // 예제: N=3, arr = [1,2,3]
        N = 3;
        arr = new int[]{1, 2, 3};
        visited = new boolean[N];
        path = new ArrayList<>();
 
        backtrack(0); // 시작 (depth=0)
    }
 
    /**
     * 백트래킹 템플릿
     * @param depth 현재 탐색 깊이 (또는 path 크기)
     */
    static void backtrack(int depth) {
        // 1. 종료 조건
        if (depth == N) { // 원하는 길이에 도달했을 때
            System.out.println(path);
            return;
        }
 
        // 2. 선택지 순회
        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;  // 이미 사용한 원소는 건너뜀
 
            // 3. 선택
            visited[i] = true;
            path.add(arr[i]);
 
            // 4. 재귀 호출 (다음 깊이 탐색)
            backtrack(depth + 1);
 
            // 5. 선택 해제 (원상복구 → "백트래킹")
            visited[i] = false;
            path.remove(path.size() - 1);
        }
    }
}
 

순열 (Permutation)

• 순서 중요, 중복 불가

import java.util.*;
 
public class Permutation {
    static int N;
    static int[] arr;
    static boolean[] visited;
    static List<Integer> path;
 
    public static void main(String[] args) {
        arr = new int[]{1, 2, 3};
        N = arr.length;
        visited = new boolean[N];
        path = new ArrayList<>();
 
        backtrack(0);
    }
 
    static void backtrack(int depth) {
        if (depth == N) { // 길이가 N인 순열 완성
            System.out.println(path);
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;
 
            visited[i] = true;
            path.add(arr[i]);
 
            backtrack(depth + 1);
 
            visited[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

조합 (Combination)

• 순서 상관 없음, 중복 불가

import java.util.*;
 
public class Combination {
    static int N, R;   // 전체 개수 N, 뽑을 개수 R
    static int[] arr;
    static List<Integer> path;
 
    public static void main(String[] args) {
        arr = new int[]{1, 2, 3, 4};
        N = arr.length;
        R = 2; // 2개 뽑기
        path = new ArrayList<>();
 
        backtrack(0, 0);
    }
 
    static void backtrack(int start, int depth) {
        if (depth == R) { // R개 뽑으면 출력
            System.out.println(path);
            return;
        }
 
        for (int i = start; i < N; i++) {
            path.add(arr[i]);
            backtrack(i + 1, depth + 1); // 다음 인덱스부터 탐색
            path.remove(path.size() - 1);
        }
    }
}
 

부분 집합

• 각 원소를 선택 or 비선택

import java.util.*;
 
public class Subset {
    static int N;
    static int[] arr;
    static List<Integer> path;
 
    public static void main(String[] args) {
        arr = new int[]{1, 2, 3};
        N = arr.length;
        path = new ArrayList<>();
 
        backtrack(0);
    }
 
    static void backtrack(int index) {
        if (index == N) { // 모든 원소 결정 끝
            System.out.println(path);
            return;
        }
 
        // 1. 현재 원소 선택
        path.add(arr[index]);
        backtrack(index + 1);
 
        // 2. 현재 원소 선택 안 함
        path.remove(path.size() - 1);
        backtrack(index + 1);
    }
}