[Java] 백트래킹 - 부분집합, 순열, 조합

백트래킹이란?

백트래킹(Backtracking)은 가능한 모든 경우를 탐색하되, 조건에 맞지 않으면 되돌아가서 다른 경우를 시도하는 알고리즘이다.

쉽게 말하면 이렇다.

"일단 해봐. 안 되면 되돌아와서 다른 거 해봐."

재귀 함수로 구현하며, 선택 → 재귀 → 선택 취소 패턴이 핵심이다.

선택      →    재귀 호출    →    선택 취소 (백트래킹)
visited[i] = true → permutation(...) → visited[i] = false

---

부분집합 vs 순열 vs 조합

	순서	개수
부분집합	상관 없음	상관 없음
순열	상관 있음	r개
조합	상관 없음	r개

예시 {1, 2, 3} 에서 2개 뽑기

순열

• 가짓수 : 6개
• 예시 : {1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}

조합

• 가짓수 : 3개
• 예시 : {1,2}, {1,3}, {2,3}

한 줄 요약

• 부분집합 : 각 원소를 포함할지 말지 결정하며 나올 수 있는 모든 집합 (빈 집합 포함!)
• 순열 : r개의 원소를 나열 (순서 중요!)
• 조합 : r개의 원소를 선택 (순서는 중요하지 않음)

---

부분집합 (Subset)

개념

{1, 2, 3} 의 모든 부분집합은 다음과 같다.

{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}  → 총 8가지 (2^3)

각 원소에 대해 포함 / 미포함 두 가지 선택만 한다.

동작 흐름

1 포함 여부 결정
├── 포함 O → 2 포함 여부 결정
│           ├── 포함 O → 3 포함 여부 결정 → {1,2,3} 출력
│           └── 포함 X → 3 포함 여부 결정 → {1,2} 출력
└── 포함 X → 2 포함 여부 결정
            ├── 포함 O → 3 포함 여부 결정 → {1,3} 출력
            └── 포함 X → ...

코드

static int[] arr = {1, 2, 3};
static boolean[] selected = new boolean[arr.length];
static int count = 0;

static void printSubset() {
    count = 0;
    subset(0);
    System.out.println("\n총 " + count + " 가지");
}

static void subset(int depth) {
    // 기저 조건 : 모든 원소에 대해 선택 여부를 결정했으면 출력
    if (depth == arr.length) {
        count++;
        System.out.print("{ ");
        for (int i = 0; i < arr.length; i++) {
            if (selected[i]) System.out.print(arr[i] + " ");
        }
        System.out.println("}");
        return;
    }

    // 현재 원소를 포함하는 경우
    selected[depth] = true;
    subset(depth + 1);

    // 현재 원소를 포함하지 않는 경우 (백트래킹)
    selected[depth] = false;
    subset(depth + 1);
}

핵심 포인트

• visited 없이 selected 배열만으로 포함 여부를 결정
• depth가 arr.length에 도달하면 하나의 부분집합 완성
• 포함 O / 포함 X 두 갈래로 재귀 → 총 2^n 가지

---

순열 (Permutation)

개념

{1, 2, 3} 에서 2개를 뽑아 순서 있게 나열한다.

{1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}  → 총 6가지 (3P2)

순서가 다르면 다른 경우다. {1,2} 와 {2,1} 은 다르다.

동작 흐름

depth=0 선택       depth=1 선택        결과
─────────────────────────────────────────
1 선택     ──→     2 선택    ──→   {1,2} ✅
           ──→     3 선택    ──→   {1,3} ✅
2 선택     ──→     1 선택    ──→   {2,1} ✅
           ──→     3 선택    ──→   {2,3} ✅
3 선택     ──→     1 선택    ──→   {3,1} ✅
           ──→     2 선택    ──→   {3,2} ✅

코드

static int count = 0;

// 편의 함수 : 배열과 r값만 넘기면 순열 실행
static void printPermutation(int[] arr, int r) {
    int[] result = new int[r];
    boolean[] visited = new boolean[arr.length];
    count = 0;

    permutation(arr, result, visited, 0, r);
    System.out.println("\n총 " + count + " 가지");
}

static void permutation(int[] arr, int[] result, boolean[] visited, int depth, int r) {
    // 기저 조건 : r개를 모두 선택했으면 출력
    if (depth == r) {
        count++;
        for (int i = 0; i < r; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
        return;
    }

    // 원본 배열의 원소를 하나씩 시도
    for (int i = 0; i < arr.length; i++) {
        // 이미 선택된 원소는 건너뜀
        if (visited[i]) continue;

        // arr[i]를 선택 : result에 넣고 visited 표시
        visited[i] = true;
        result[depth] = arr[i];

        // 다음 깊이로 재귀 호출
        permutation(arr, result, visited, depth + 1, r);

        // 선택 취소 (백트래킹)
        visited[i] = false;
    }
}

핵심 포인트

• visited 배열로 같은 원소를 두 번 쓰는 것을 방지
• depth == r 이 되면 r개 선택 완료 → 출력
• 재귀 후 visited[i] = false 로 되돌려야 다른 경우 탐색 가능

---

조합 (Combination)

개념

{1, 2, 3} 에서 2개를 뽑는다. 순서는 상관없다.

{1,2}, {1,3}, {2,3}  → 총 3가지 (3C2)

순서가 달라도 같은 경우다. {1,2} 와 {2,1} 은 같다.

순열과의 차이점

순열은 모든 원소를 매번 처음부터 탐색하지만, 조합은 이미 선택한 원소보다 뒤에 있는 원소만 탐색한다.

순열 : 1 선택 후 → {2, 3} 탐색 / 2 선택 후 → {1, 3} 탐색  (앞으로도 감)
조합 : 1 선택 후 → {2, 3} 탐색 / 2 선택 후 → {3} 탐색     (앞으로 안 감)

이게 핵심이다. start 변수로 탐색 시작 위치를 앞으로 당기지 않는다.

동작 흐름

depth=0 선택       depth=1 선택        결과
─────────────────────────────────────────
1 선택(start=1) ──→  2 선택  ──→   {1,2} ✅
               ──→  3 선택  ──→   {1,3} ✅
2 선택(start=2) ──→  3 선택  ──→   {2,3} ✅
3 선택(start=3) ──→  (탐색할 원소 없음, 종료)

코드

static int count = 0;

// 편의 함수 : 배열과 r값만 넘기면 조합 실행
static void printCombination(int[] arr, int r) {
    int[] result = new int[r];
    count = 0;

    combination(arr, result, 0, 0, r);
    System.out.println("\n총 " + count + " 가지");
}

static void combination(int[] arr, int[] result, int start, int depth, int r) {
    // 기저 조건 : r개를 모두 선택했으면 출력
    if (depth == r) {
        count++;
        for (int i = 0; i < r; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
        return;
    }

    // start부터 탐색 (이전 원소는 다시 보지 않음)
    for (int i = start; i < arr.length; i++) {
        result[depth] = arr[i];

        // 다음 탐색은 i+1부터 (중복 방지)
        combination(arr, result, i + 1, depth + 1, r);
    }
}

핵심 포인트

• visited 배열이 필요 없음 → start로 탐색 범위를 제한
• 재귀 호출 시 i + 1 을 넘겨서 현재 원소보다 뒤만 탐색
• 백트래킹은 자동으로 됨 (result 덮어쓰기 방식)

---

세 가지 비교 정리

	부분집합	순열	조합
핵심 변수	selected[]	visited[]	start
탐색 범위	전체 (포함/미포함)	전체 (visited 체크)	start 이후만
결과 수	2^n	nPr	nCr
백트래킹	selected = false	visited = false	자동 (덮어쓰기)

---

마무리

백트래킹의 핵심은 선택 → 재귀 → 선택 취소 패턴이다.

세 가지 모두 같은 뼈대를 가지고 있고, 차이는 어떻게 중복을 방지하느냐다.

• 부분집합 : 포함/미포함 두 갈래로 나눔
• 순열 : visited로 이미 쓴 원소 막음
• 조합 : start로 탐색 범위를 앞으로 당기지 않음

이 패턴에 익숙해지면 백트래킹 문제의 대부분을 풀 수 있다.