Combination Sum

조합은 각 후보를 몇 개씩 사용하는지로 완전히 설명할 수 있습니다. [6, 2, 3]에서 목표값이 8일 때, 답 [2, 3, 3]은 2 하나와 3 두 개를 사용하고 6은 사용하지 않습니다. 따라서 모든 답을 찾는 한 가지 방법은 각 후보의 가능한 개수를 모두 시도하고, 합계가 정확히 target인 선택만 남기는 것입니다. 후보 c는 최대 target / c번 들어갈 수 있으므로, 개수는 0부터 그 상한까지입니다.

후보를 정렬한 뒤 후보마다 한 단계씩 있는 결정 트리를 떠올려 보세요. i번째 단계에서는 i번째 값의 복사본을 몇 개 선택할지 결정하고, 맨 아래의 각 리프는 개수를 완전히 정한 하나의 선택입니다. 각 중복집합은 개수 목록이 정확히 하나이므로, 같은 조합이 두 번 발견되지 않습니다. 가장 큰 개수부터 시도하면 요구된 순서도 얻을 수 있습니다. 두 답이 어떤 값의 개수에서 처음 달라질 때, 그 작은 값을 더 많이 포함한 답에는 다른 답이 이미 더 큰 값을 포함하는 위치에도 그 작은 값이 남아 있으므로, 그 답이 먼저 옵니다.

문제는 트리의 크기입니다. 리프의 개수는 모든 후보에 대해 target / c + 1을 곱한 값입니다. 정렬된 [2, 3, 6]에서 목표값이 8인 경우, 답은 3개지만 리프는 5 × 3 × 2 = 30개입니다. target / 2보다 큰 후보는 최대 한 번만 들어갈 수 있는데도 리프 수를 두 배로 늘리므로, 그런 후보만 40개 있어도 리프는 2^40개, 즉 약 10^12개가 됩니다. 큰 테스트는 이런 식으로 만들어져 있어 이 방법으로는 끝까지 처리할 수 없습니다.

각 조합은 값을 하나씩, 직접 적을 때처럼 오름차순으로 만듭니다. 시작 인덱스가 이 순서를 유지합니다. nums[i]를 넣은 다음에는 후보 값을 반복해서 사용할 수 있으므로 다음 값으로 다시 nums[i]를 선택할 수도 있고, 그보다 뒤의 값을 선택할 수도 있지만, 앞선 값은 선택할 수 없습니다. 따라서 인덱스 i를 넣은 호출은 i부터만 반복합니다. 각 조합에는 오름차순이 정확히 하나뿐이므로 트리에서도 경로가 정확히 하나이며, [3, 2, 3]과 같은 중복 조합은 만들어지지 않습니다.

정렬된 [2, 3, 6]과 target 8에 대한 전체 트리는 다음과 같습니다. 루트에는 8이 남아 있고 2, 3, 6을 시도합니다. 2 아래에는 6이 남습니다. 2, 2 아래에는 4가 남고, 2, 2, 2 아래에는 2가 남습니다. 여기에 2를 한 번 더 넣으면 정답 [2, 2, 2, 2]이 됩니다. 2, 2, 3 아래에는 1이 남으므로 더 진행할 수 없습니다. 2, 3 아래에는 3이 남아 있으며 3과 6만 시도할 수 있고, 3을 선택하면 [2, 3, 3]이 됩니다. 2, 6 아래에는 남은 값이 없습니다. 즉 [2, 6]입니다. 3 아래에서는 3과 6만 시도할 수 있으며, 3, 3 아래에는 2가 남지만 어느 값으로도 채울 수 없습니다. 6 아래에는 2가 남으며 6만 시도할 수 있습니다. 총 12번의 호출로, 첫 번째 방법에서의 30개 리프 노드와 비교됩니다.

정렬하면 막다른 경로에서 일찍 멈출 수 있습니다. nums[i]가 남은 값보다 크면 그 뒤의 모든 값도 더 크므로, 나머지를 확인하는 대신 break로 루프를 빠져나옵니다. 위 트리에서 1이 남은 2, 2, 3 노드는 3을 확인하고 들어맞지 않는다는 것을 알게 되므로 6은 확인하지 않습니다. 탐색은 합이 여전히 target 이하인 접두 경로만 방문합니다. 그래서 첫 번째 방법을 막히게 하는 큰 테스트도 여기서는 몇천 번의 호출만으로 처리됩니다.

출력 순서도 같은 순회에서 나옵니다. 각 단계에서 루프는 더 작은 값부터 시도하며 모든 조합은 오름차순으로 작성됩니다. 두 답은 경로가 갈라지는 단계에서 처음 달라지며, 그 단계에서 더 작은 값을 선택한 경로를 먼저 탐색하므로 답은 사전식 순서로 나옵니다. 값이 양수이고 두 조합의 합이 같으므로 한 조합이 다른 조합의 접두사가 될 수는 없습니다.