백 트래킹 Q43: 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기 - JAVA

[문제]

정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 solution() 함수를 작성하세요.

 

제약조건

백트래킹을 활용해야한다.

숫자 조합은 오름차순으로 정렬되어야 한다.

같은 숫자는 한 번만 선택할 수 있다.

N은 1 이상 10 이하인 정수이다.

입출력의 예

N	result
5	[ [1, 2, 3, 4], [1, 4, 5], [2, 3, 5] ]
2	[ ]
7	[ [1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5], [3, 7], [4, 6] ]

---

[해설]

1. 문제 이해

본 문제는 1부터 N까지의 자연수 중 중복 없이 숫자를 선택하여 그 합이 정확히 10이 되는 모든 조합을 찾는 것입니다.

• 제약 사항: 조합 내 숫자는 오름차순이어야 하며, 동일한 숫자를 재사용할 수 없습니다.
• 핵심 조건: 1 <= N <= 10 이므로 탐색 범위가 좁아 효율적인 백트래킹이 가능합니다.

2. 핵심 아이디어

이 문제의 핵심은 전체 탐색(DFS)을 진행하되, 불필요한 경로를 미리 차단하는 가지치기(Pruning)에 있습니다.

• 상태 트리 탐색: start 인수를 통해 현재 숫자보다 큰 숫자만 선택하도록 하여 자연스럽게 오름차순을 유지하고 중복 조합(예: [1,4,5]와 [5,4,1])을 방지합니다.
• 유망성 검사 (가지치기): 현재까지의 합(sum)에 다음 숫자(i)를 더했을 때 10을 초과하면, 그 이후의 루프는 확인해 볼 필요도 없이 break로 종료합니다. 이는 실행 시간을 대폭 단축시킵니다.
• 복구 (Backtracking): list.remove(list.size() - 1)를 통해 선택했던 숫자를 제거함으로써, 이전 상태로 돌아가 다른 숫자의 조합을 탐색할 수 있도록 합니다.

---

[코드]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Q43 {
    static int N;
    static List<Integer> list = new ArrayList<>();

    public static void solution(int start, int sum) {
        if (sum == 10) {
            System.out.println(list);
            return;
        }

        for (int i = start; i <= N; i++) {

            if (sum + i > 10) break;

            list.add(i);
            solution(i + 1, sum + i);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        sc.close();

        solution(1, 0);
    }
}