a-072-combination-sum2026-07-28mediumleetcode #39neetcode150

조합의 합

#array#backtracking

문제

· problem

P.a-072-combination-sum

조합의 합

서로 다른 정수로 이루어진 배열 candidates와 정수 target이 주어졌을 때, candidates에서 선택한 수들의 합이 target이 되는 모든 고유한 조합의 리스트를 반환하세요. 조합은 어떤 순서로든 반환할 수 있습니다. 같은 수를 candidates에서 무제한으로 선택할 수 있습니다. 두 조합은 선택된 수 중 적어도 하나의 빈도가 다르면 서로 다른 조합입니다. 테스트 케이스는 주어진 입력에 대해 target을 만드는 고유한 조합의 개수가 150개 미만이 되도록 생성됩니다.

제약

· 1 ≤ candidates.length ≤ 30
· 2 ≤ candidates[i] ≤ 40
· All elements of candidates are distinct
· 1 ≤ target ≤ 40

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[2,3,6,7]
7

[[2,2,3],[7]]

example 2input → output

[2,3,5]
8

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

example 3input → output

[2]
1

[]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
같은 숫자를 여러 번 사용할 수 있나요?
☐
두 조합이 '고유하다'는 것의 정의는 무엇인가요?
☐
결과 조합들을 정렬된 순서로 반환해야 하나요?
☐
각 후보 숫자가 최대 몇 번까지 사용될 수 있나요?
☐
candidates 배열에 중복된 값이 있을 수 있나요?
☐
조합 [2,2,3]과 [2,3,2]는 다른 조합으로 간주되나요?
☐
target을 정확히 만들 수 없으면 빈 리스트를 반환하나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 결과 저장소 초기화

○

res = []

○

res = None

○

res = set()

step 2· 기저 조건: 목표값 도달 검사│ 중첩

○

if total == target:

○

if total > target:

○

if total >= target:

step 3· 조합을 결과에 추가│ │ 중첩

○

res.append(cur.copy())

○

res.append(cur)

○

res.append(tuple(cur))

step 4· 가지 자르기: 유효하지 않은 상태 제거│ 중첩

○

if i >= len(candidates) or total > target:

○

if i >= len(candidates) or total >= target:

○

if i > len(candidates) or total > target:

step 5· 현재 후보 포함하기│ │ 중첩

○

cur.append(candidates[i])

○

cur.append(i)

○

candidates.append(cur)

step 6· 재귀: 같은 후보를 재사용하도록│ │ 중첩

○

dfs(i, cur, total + candidates[i])

○

dfs(i + 1, cur, total + candidates[i])

○

dfs(i, cur, total)

step 7· 백트래킹 후 다음 후보로 이동│ │ 중첩

○

dfs(i + 1, cur, total)

○

dfs(i, cur, total)

○

dfs(i + 2, cur, total)

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        res = []

        def dfs(i, cur, total):

            if total == target:

                res.append(cur.copy())

                return

            if i >= len(candidates) or total > target:

                return

            cur.append(candidates[i])

            dfs(i, cur, total + candidates[i])

            cur.pop()

            dfs(i + 1, cur, total)

        dfs(0, [], 0)

        return res

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[2,3,6,7]
7

→

[[2,2,3],[7]]

case 2

[2,3,5]
8

→

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

case 3

[2]
1

→

[]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.