Combination Sum

Q: Combination Sum의 시간 복잡도는 얼마인가요?

백트래킹 탐색은 지수 시간 복잡도를 가집니다. 후보가 n 개이고, 목표값이 t 이며 가장 작은 후보가 m 일 때, 하나의 조합에는 최대 t/m 개의 값이 들어가고 각 값마다 선택지는 최대 n 개입니다. 따라서 시간 복잡도는 O(n^(t/m)) 입니다. 경로와 호출 스택에 필요한 추가 공간은 O(t/m) 이며, 여기에 출력 공간이 더해집니다.

Q: Combination Sum에서는 왜 i + 1 이 아니라 i 로 재귀 호출하나요?

i 로 재귀 호출하면 다음 값도 같은 후보가 되므로, 하나의 값을 두 번 이상 사용할 수 있습니다. i + 1 로 재귀 호출하면 그 값을 지나치므로, 각 후보는 최대 한 번만 사용할 수 있습니다.

Q: 조합 합(Combination Sum) 문제를 동적 프로그래밍으로 풀 수 있나요?

네. 0부터 target 까지 각 합계에 대해 그 합계에 도달하는 조합을 유지하고, 한 번에 후보 하나씩 추가하여 각 목록이 오름차순을 유지하도록 합니다. 막다른 길을 두 번 탐색하지는 않지만, 모든 합계에 대한 부분 조합을 전부 저장하므로 훨씬 더 많은 메모리를 사용합니다. 출력 자체가 지수적으로 커질 수 있으므로, 일반적으로 백트래킹을 사용합니다.

보통백트래킹

+10

서로 다른 양의 정수로 이루어진 목록 candidates와 양의 정수 target이 주어집니다. 각 후보를 원하는 만큼 사용하여 합이 정확히 target이 되는 모든 조합을 찾으세요. [2, 3, 3]과 [3, 2, 3]은 같은 조합입니다.

각 조합은 오름차순으로 반환하고, 조합들은 사전순으로 반환하세요. 두 조합이 처음으로 서로 다른 위치에서 더 작은 값을 가진 조합을 먼저 반환합니다.

함수

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: 순서에 상관없이 원하는 만큼 사용할 수 있는 서로 다른 값
targetinteger: 모든 조합의 합계가 정확히 도달해야 합니다
반환값integer-2d-array: target의 합이 되는 모든 조합을 오름차순으로 나열하고, 사전순으로 정렬합니다

제약 조건

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
candidates의 모든 값은 서로 다르며, 특정한 순서는 없습니다.
최소 하나의 조합은 target에 도달하며, 최대 150개의 조합이 도달합니다.

예제

입력: candidates = [6, 2, 3]target = 8
출력: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
설명: 2가 네 개 있는 경우, 2 + 3 + 3과 2 + 6은 모두 8이 되며, 두 번째 값에 따라 정렬됩니다. 2가 없으면 3과 6만 남고, 이들의 합은 3의 배수인데 8은 그렇지 않습니다.

입력: candidates = [5, 3, 4]target = 11
출력: [[3, 3, 5], [3, 4, 4]]
설명: 3 + 3 + 5와 3 + 4 + 4는 모두 11이 되고, [3, 3, 5]의 두 번째 값인 3이 4보다 작으므로 먼저 나옵니다. 4와 5만 조합해서는 11을 만들 수 없습니다.

후속 질문

각 후보는 이제 최대 한 번만 사용할 수 있고, candidates에는 중복된 값이 들어 있을 수 있습니다. 조합이 두 번 나타나지 않도록 검색을 어떻게 변경하나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

같은 조합을 두 번 만드는 것이 함정입니다. 2, 3, 3과 3, 2, 3은 하나의 답입니다. 각 조합을 오름차순으로 만들어 정확히 하나의 경로만 갖게 하고, 후보를 정렬하여 다음 값이 남은 값보다 커지는 즉시 분기를 멈추세요.

각 후보에 대해 모든 개수를 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

조합은 각 후보를 몇 개씩 사용하는지로 완전히 표현됩니다. [2, 3, 3]은 2 하나와 3 두 개를 사용하고 6은 사용하지 않는다는 뜻입니다. 정렬된 각 후보에 대해 target / c부터 0까지 모든 개수를 시도하고, 합계가 정확히 target이 되는 선택을 유지하세요. 각 조합에는 개수 목록이 하나씩만 있으므로 같은 조합이 두 번 나오지 않습니다. 개수가 큰 것부터 시도하면 사전식 순서가 됩니다. 두 답이 처음으로 달라지는 지점에서, 어떤 값이 더 많이 포함된 답은 그 값을 유지하고 다른 답은 더 큰 값을 포함하기 때문입니다.

[2, 3, 6]과 target 8의 경우, 답은 3개지만 리프는 5 × 3 × 2 = 30개입니다. target / 2보다 큰 각 후보는 리프 수를 두 배로 늘리므로, 이런 후보가 40개라면 2^40, 즉 약 10^12개가 됩니다.

알고리즘

후보를 정렬하고 각 값마다 하나의 개수를 유지합니다.
choose(i, total)에서 target / nums[i]부터 0까지 각 개수 k를 시도하고 choose(i + 1, total + k × nums[i])를 호출합니다.
모든 값의 개수가 정해지면 total이 target과 같은 경우 조합을 유지하고 개수로 조합을 작성합니다.
choose(0, 0)을 호출합니다.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

오름차순으로 역추적하고 가지치기하기

핵심 아이디어

nums[i]를 배치한 후 다음 값은 다시 nums[i]이거나 그 이후의 값일 수 있지만, 앞선 값일 수는 없습니다. 조합은 오름차순 순서가 정확히 하나이므로 경로도 하나뿐이며, [3, 2, 3]은 절대 만들어지지 않습니다.

정렬된 [2, 3, 6]과 target 8의 경우, 경로 2, 2, 2, 2와 2, 3, 3, 그리고 2, 6은 8에 도달합니다. 경로 2, 2, 3은 1이 남아 6을 살펴보지 않고 멈추며, 3, 3은 2가 남는데 어떤 값도 이에 맞지 않습니다. 이는 counting의 30개 리프와 비교해 12번의 호출입니다.

각 단계에서 루프는 더 작은 값부터 시도하므로 답이 사전식 순서로 나옵니다. 값이 양수이고 둘 다 같은 합에 도달하므로 어떤 답도 다른 답의 접두사가 되지 않습니다.

알고리즘

후보들을 정렬합니다.
backtrack(start, remaining)에서 remaining이 0이면 공유된 path의 복사본을 저장합니다.
그렇지 않으면 start부터 i를 반복합니다. nums[i] > remaining이면 중단합니다. 뒤에 오는 모든 값이 더 크기 때문입니다.
nums[i]를 추가하고, backtrack(i, remaining - nums[i])를 호출한 다음, 해당 값을 제거합니다.
backtrack(0, target)을 호출하고 저장된 조합을 반환합니다.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

함정과 경계 사례

현재 인덱스부터 시작하는 대신 각 단계에서 모든 후보를 순회합니다. 그러면 [2, 3, 3], [3, 2, 3], [3, 3, 2]가 서로 다른 세 가지 답으로 나옵니다.
i 대신 i + 1로 재귀 호출합니다. 그러면 각 값이 한 번만 나타날 수 있으므로 [2, 2, 2, 2]가 누락됩니다.
복사본 대신 path 자체를 저장합니다. 그러면 저장된 모든 답이 같은 리스트가 되며, 역추적이 끝날 때쯤 이 리스트는 비워져 있습니다.
정렬하지 않은 후보에 break를 사용합니다. [6, 2, 3]이 있고 남은 값이 2일 때, 루프는 6에서 멈춰 2를 시도하지 않습니다.

자주 묻는 질문3

Combination Sum의 시간 복잡도는 얼마인가요?

백트래킹 탐색은 지수 시간 복잡도를 가집니다. 후보가 n개이고, 목표값이 t이며 가장 작은 후보가 m일 때, 하나의 조합에는 최대 t/m개의 값이 들어가고 각 값마다 선택지는 최대 n개입니다. 따라서 시간 복잡도는 O(n^(t/m))입니다. 경로와 호출 스택에 필요한 추가 공간은 O(t/m)이며, 여기에 출력 공간이 더해집니다.

Combination Sum에서는 왜 <code>i + 1</code>이 아니라 <code>i</code>로 재귀 호출하나요?

i로 재귀 호출하면 다음 값도 같은 후보가 되므로, 하나의 값을 두 번 이상 사용할 수 있습니다. i + 1로 재귀 호출하면 그 값을 지나치므로, 각 후보는 최대 한 번만 사용할 수 있습니다.

조합 합(Combination Sum) 문제를 동적 프로그래밍으로 풀 수 있나요?

네. 0부터 target까지 각 합계에 대해 그 합계에 도달하는 조합을 유지하고, 한 번에 후보 하나씩 추가하여 각 목록이 오름차순을 유지하도록 합니다. 막다른 길을 두 번 탐색하지는 않지만, 모든 합계에 대한 부분 조합을 전부 저장하므로 훨씬 더 많은 메모리를 사용합니다. 출력 자체가 지수적으로 커질 수 있으므로, 일반적으로 백트래킹을 사용합니다.

def combinationSum(candidates, target):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

candidates = [6, 2, 3]
target = 8

예상 출력

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]