[알고리즘] 백트래킹(Backtracking)

 

백트래킹으로 조합과 순열 구하기

프로그래밍 문제를 풀다 보면, 특정 수나 문자열을 이용해 모든 가능한 경우의 수를 만들어야 하는 경우가 많다.

이럴 때 사용되는 대표적인 알고리즘이 바로 백트래킹(Backtracking)이다.

 

---

백트래킹이란?

백트래킹은 가능한 모든 경우의 수를 시도하면서, 불필요한 가지는 미리 쳐내는 방식이다.

특히 조합, 순열과 같이 특정 조건에 맞는 모든 조합을 만들어야 할 때 매우 유용하게 사용된다.

 

---

백트래킹으로 구현하는 각 경우

1. 조합(Combination)

void combination(int[] arr, int start, int depth, int r, List<Integer> result) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = start; i < arr.length; i++) {
        result.add(arr[i]);
        combination(arr, i + 1, depth + 1, r, result);
        result.remove(result.size() - 1);
    }
}

특징

 

• 순서를 고려하지 않음
• 중복 없이 r개 선택
• start 인덱스를 사용해 앞에 뽑은 요소 이후만 탐색함

 

사용 예

• 로또 번호 조합, 부분집합 조합, 메뉴 구성 등
• (1,2)와 (2,1)은 같은 것으로 보고 하나만 생성함

---

2. 중복 조합 (Combination with Repetition)

void combinationWithRepetition(int[] arr, int start, int depth, int r, List<Integer> result) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = start; i < arr.length; i++) {
        result.add(arr[i]);
        combinationWithRepetition(arr, i, depth + 1, r, result); // i 그대로
        result.remove(result.size() - 1);
    }
}

특징

 

• 순서는 무시
• 같은 요소를 여러 번 선택 가능
• start를 그대로 넘김 (i → i)

 

사용 예

• 중복 허용하는 조합: 동전 조합, 사탕 뽑기 등
• (1,1), (1,2), (2,2)처럼 (1,1), (2,2) 중복조합을 만들 수 있음

---

 

3. 순열 (Permutation)

void permutation(int[] arr, boolean[] visited, int depth, int r, List<Integer> result) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            result.add(arr[i]);
            permutation(arr, visited, depth + 1, r, result);
            visited[i] = false;
            result.remove(result.size() - 1);
        }
    }
}

특징

• 순서가 중요
• 중복 없이 r개 선택
• 방문 여부(visited[])를 통해 중복 방지

사용 예

• 경로 탐색, 단어 조합, 좌석 배치 등
• 조합과 달리 (1,2)와 (2,1)을 서로 다르게 봄

---

4. 중복 순열 (Permutation with Repetition)

void permutationWithRepetition(int[] arr, int depth, int r, List<Integer> result) {
    if (depth == r) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        result.add(arr[i]);
        permutationWithRepetition(arr, depth + 1, r, result);
        result.remove(result.size() - 1);
    }
}

특징

• 순서 중요 + 중복 허용
• 중복 방지 안 함 → visited[] 필요 없음

사용 예

• 비밀번호 조합, 중복 가능한 코드 생성 등
• 순열보다 더 많은 경우의 수가 나옴
• 중복 조합과 달리 순서도 고려함 (1,2) ≠ (2,1)

---

✅ 조합 vs 순열 vs 중복 조합 vs 중복 순열 정리표

유형	순서 고려	중복 허용	예시	경우의 수 공식
조합 (Combination)	✖	✖	(1,2)	nCr = n! / (r!(n−r)!)
중복 조합 (Comb. w/ Repetition)	✖	✔	(1,1), (1,2), (2,2)	nHr = (n+r−1)! / (r!(n−1)!)
순열 (Permutation)	✔	✖	(1,2), (2,1)	nPr = n! / (n−r)!
중복 순열 (Perm. w/ Repetition)	✔	✔	(1,1), (1,2), (2,1), (2,2)	n^r