백트래킹 — 순열/조합

관련 문제

문제	난이도	핵심
15649번 — N과 M (1)	실버 III	순열
15650번 — N과 M (2)	실버 III	조합
15651번 — N과 M (3)	실버 III	중복순열
15652번 — N과 M (4)	실버 III	중복조합
9663번 — N-Queen	골드 IV	백트래킹 응용
1182번 — 부분수열의 합	실버 II	백트래킹 응용

---

1. 백트래킹이란?

DFS + 가지치기. 조건에 맞지 않으면 즉시 되돌아와서 불필요한 탐색을 줄인다.

DFS        = 가능한 모든 경로를 탐색
백트래킹   = DFS + 조건에 안 맞으면 즉시 포기 (가지치기)

핵심은 선택 → 탐색 → 되돌리기 3단계다.

visited[i] = true;   // 선택
dfs(depth + 1);      // 탐색
visited[i] = false;  // 되돌리기 ← 백트래킹의 핵심

---

2. 4가지 패턴 비교

유형	백준	중복 허용	순서 중요	visited	start
순열	15649	X	O	필요	없음
조합	15650	X	X	불필요	i+1
중복순열	15651	O	O	불필요	없음
중복조합	15652	O	X	불필요	i

---

3. 코드 — 핵심 차이만 비교

순열 (15649)

같은 수 사용 불가, 순서 있음. visited로 중복 방지.

static void dfs(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) sb.append(arr[i] + " ");
        sb.append("\n");
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            arr[depth] = i;
            dfs(depth + 1);       // start 없음, 매번 1부터
            visited[i] = false;
        }
    }
}

조합 (15650)

같은 수 사용 불가, 순서 없음. start로 앞 숫자로 되돌아가지 못하게 막음.

static void dfs(int depth, int start) {
    if (depth == M) {
        for (int i = 0; i < M; i++) sb.append(arr[i] + " ");
        sb.append("\n");
        return;
    }
    for (int i = start; i <= N; i++) {
        arr[depth] = i;
        dfs(depth + 1, i + 1);    // 다음은 i+1부터
    }
}

중복순열 (15651)

같은 수 사용 가능, 순서 있음. visited도 start도 불필요.

static void dfs(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) sb.append(arr[i] + " ");
        sb.append("\n");
        return;
    }
    for (int i = 1; i <= N; i++) {
        arr[depth] = i;
        dfs(depth + 1);           // visited도 start도 없음
    }
}

중복조합 (15652)

같은 수 사용 가능, 순서 없음. start를 i로 넘겨서 같은 수 재사용 허용.

static void dfs(int depth, int start) {
    if (depth == M) {
        for (int i = 0; i < M; i++) sb.append(arr[i] + " ");
        sb.append("\n");
        return;
    }
    for (int i = start; i <= N; i++) {
        arr[depth] = i;
        dfs(depth + 1, i);        // 다음도 i부터 (같은 수 허용)
    }
}

---

4. N=3, M=2 결과 비교

순열	조합	중복순열	중복조합
1 2	1 2	1 1	1 1
1 3	1 3	1 2	1 2
2 1	2 3	1 3	1 3
2 3		2 1	2 2
3 1		2 2	2 3
3 2		2 3	3 3
		3 1
		3 2
		3 3

---

5. 정리

백트래킹 = 구현 방법
순열/조합 = 결과물

기본 틀 (순열/조합) + 가지치기 조건 = 응용 백트래킹

백트래킹 응용 문제(N-Queen, 부분수열 합 등)는 모두 위 4가지 기본 틀에서 출발한다. 기본 틀을 완벽히 이해하는 것이 선행되어야 한다.