Leetcode 39 조합 합

Source: Dev.to

위에 제공된 소스 링크 외에 번역할 텍스트가 없습니다. 번역을 원하는 본문을 제공해 주시면 한국어로 번역해 드리겠습니다.

Problem Statement

서로 다른 정수들로 이루어진 배열 candidates와 목표 정수 target이 주어지면, 선택한 숫자들의 합이 target이 되는 모든 고유 조합을 반환합니다.
각 후보를 무한히 사용할 수 있습니다. 두 조합은 최소 하나의 숫자 빈도가 다르면 서로 다른 것으로 간주합니다.

예시: [2,3,3], [3,2,3], 그리고 [3,3,2]는 동일한 고유 조합을 나타냅니다.

예시

입력

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

출력

[[2,2,2,2], [2,3,3], [3,5]]

수학적 공식화

문제는 다음과 같은 비음수 정수 x, y, z를 찾는 것으로 표현할 수 있다.

2·x + 3·y + 5·z = 8

해결책

class Solution:
    def combinationSum(self, candidates, target):
        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                # 유효한 조합을 찾음
                results.append(list(comb))   # 얕은 복사
                return
            if remain < 0:
                # 합이 초과되어 이 경로 탐색을 중단
                return

            for i in range(start, len(candidates)):
                # 후보 선택
                comb.append(candidates[i])
                # 같은 시작 인덱스로 계속 탐색 (재사용 허용)
                backtrack(remain - candidates[i], comb, i)
                # 백트래킹
                comb.pop()

        backtrack(target, [], 0)
        return results

일반적인 함정

깊이‑우선 탐색 워크스루

예제(candidates = [2,3,5], target = 8)에 대한 재귀 트리는 아래와 같이 나타내며(각 노드는 i – 인덱스, v – 값, remain, start를 보여줍니다).

root (target: 8)
└── [i:0, v:2] remain: 6, start: 0
    ├── [i:0, v:2] remain: 4, start: 0
    │   ├── [i:0, v:2] remain: 2, start: 0
    │   │   ├── [i:0, v:2] remain: 0, start: 0 ── Success → [2,2,2,2]
    │   │   ├── [i:1, v:3] remain: -1 ── Fail
    │   │   └── [i:2, v:5] remain: -3 ── Fail
    │   ├── [i:1, v:3] remain: 1, start: 1
    │   │   ├── [i:1, v:3] remain: -2 ── Fail
    │   │   └── [i:2, v:5] remain: -4 ── Fail
    │   └── [i:2, v:5] remain: -1 ── Fail
    ├── [i:1, v:3] remain: 3, start: 1
    │   ├── [i:1, v:3] remain: 0 ── Success → [2,3,3]
    │   └── [i:2, v:5] remain: -2 ── Fail
    └── [i:2, v:5] remain: 1, start: 2
        └── [i:2, v:5] remain: -4 ── Fail
└── [i:1, v:3] remain: 5, start: 1
    ├── [i:1, v:3] remain: 2, start: 1
    │   ├── [i:1, v:3] remain: -1 ── Fail
    │   └── [i:2, v:5] remain: -3 ── Fail
    └── [i:2, v:5] remain: 0 ── Success → [3,5]
└── [i:2, v:5] remain: 3, start: 2
    └── [i:2, v:5] remain: -2 ── Fail

Source: …

참조 표