백트래킹 4대 패턴 정리

1. 포함 / 미포함 (Subset DFS)

부분수열/부분집합을 가장 직관적으로 뽑는 패턴.
"현재 원소를 포함한다 / 안 한다" 두 갈래로 분기하는 것이 특징.

void dfs(int idx, int sum, int picked) {
    if (idx == N) {
        if (picked > 0 && sum == S) ans++;
        return;
    }
    // 현재 원소 포함
    dfs(idx + 1, sum + arr[idx], picked + 1);
    // 현재 원소 미포함
    dfs(idx + 1, sum, picked);
}

• 공집합 제외: picked > 0 조건으로 해결
• 모든 순서는 idx로 자동 처리 -> visited 불필요
• 부분집합 개수: 2^N

---

2. 조합 (start index 이용)

for문 안에서 start를 앞으로 밀어가며 선택.

void comb(int start, int sum) {
    for (int i = start; i < N; i++) {
        int nextSum = sum + arr[i];
        if (nextSum == S) ans++;
        comb(i + 1, nextSum);
    }
}

• 중복 방지: i + 1로 다음 호출
• 선택 시 바로 검사 가능

---

3. 순열 (visited 배열)

순서가 중요하고, 중복 없는 경우.

void perm(int depth) {
    if (depth == M) {
        // 출력 or 검사
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            out[depth] = arr[i];
            perm(depth + 1);
            visited[i] = false;
        }
    }
}

• visited 필수
• 순서대로 모든 경우 탐색

---

4. 중복 순열 (visited 없이)

순서 중요 + 중복 허용

void dupPerm(int depth) {
    if (depth == M) {
        // 출력 or 검사
        return;
    }
    for (int i = 0; i < N; i++) {
        out[depth] = arr[i];
        dupPerm(depth + 1);
    }
}

• visited 없음
• 모든 원소 매번 선택 가능

---

패턴 선택 기준

문제 조건	패턴
순서 상관 X, 중복 X	포함/미포함 DFS or 조합
순서 상관 O, 중복 X	순열
순서 상관 O, 중복 O	중복 순열
N 작고 경우의 수 모두 필요	위 네 가지 중 조건 맞춰 선택

---

백준 연습 문제 추천

Day	패턴	번호	문제 이름	난이도	링크	체크
1	포함/미포함	1182	부분수열의 합	실버 2	링크	✅
1	조합	15650	N과 M (2)	실버 3	링크	✅
1	순열(중복X)	15649	N과 M (1)	실버 3	링크	✅
1	중복 순열	15651	N과 M (3)	실버 3	링크	✅
2	포함/미포함	6603	로또	실버 2	링크	✅
2	조합	15655	N과 M (6)	실버 3	링크	✅
2	순열(중복X)	10974	모든 순열	실버 3	링크	✅
2	중복 순열	15656	N과 M (7)	실버 3	링크	✅
3	포함/미포함	14225	부분수열의 합	실버 1	링크	✅
3	조합	1759	암호 만들기	골드 5	링크	✅
3	순열(중복X)	10819	차이를 최대로	실버 2	링크	✅
3	중복 순열	16922	로마 숫자 만들기	실버 3	링크	✅