a-075-combination-sum-ii2026-07-31mediumleetcode #40neetcode150

조합의 합 II

#array#backtracking

↗ leetcode #40 · a-075-combination-sum-ii

문제

· problem

P.a-075-combination-sum-ii

조합의 합 II

후보 숫자들의 배열(candidates)과 목표 숫자(target)가 주어질 때, candidates에서 합이 target이 되는 모든 고유한 조합을 찾으세요. candidates의 각 숫자는 한 조합에서 최대 한 번만 사용할 수 있습니다. 주의: 결과 집합은 중복된 조합을 포함해서는 안 됩니다.

제약

· 1 ≤ candidates.length ≤ 100
· 1 ≤ candidates[i] ≤ 50
· 1 ≤ target ≤ 30

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

입출력 예시

example 1input → output

[10,1,2,7,6,1,5]
8

[[1,1,6],[1,2,5],[1,7],[2,6]]

example 2input → output

[2,5,2,1,2]
5

[[1,2,2],[5]]

사전 사고

· pre-solve

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

☐
같은 인덱스의 숫자를 한 조합에서 여러 번 사용할 수 있나요?
☐
입력 배열에 중복된 숫자가 있으면 결과에 중복된 조합이 나타날 수 있나요?
☐
결과에 포함된 각 조합이 정렬된 순서여야 하나요?
☐
입력 배열에 같은 값이 두 개 있으면 각각을 다른 요소로 취급하나요?
☐
한 번의 재귀 호출에서 이전에 선택한 숫자를 다시 선택할 수 있나요?
☐
정렬하지 않은 배열도 이 알고리즘으로 올바른 답을 얻을 수 있나요?
☐
`cur.copy()` 대신 `cur`를 직접 추가해도 되나요?

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

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

논리 구조

· logic

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

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

step 1· 입력 정렬

○

candidates.sort()

○

candidates.reverse()

○

sorted_candidates = sorted(candidates)

step 2· 기저 경우: 유효한 조합 발견│ 중첩

○

res.append(cur.copy())

○

res.append(cur)

○

if target == 0: return res.append(cur.copy())

step 3· 가지 제거: 합 초과│ 중첩

○

if target <= 0:

○

if target < 0: res.append(cur.copy()); return

○

if target <= 0: return

step 4· 중복 후보자 건너뛰기│ │ 중첩

○

if candidates[i] == prev:

○

if i > 0 and candidates[i] == candidates[i-1]: continue

○

if candidates[i] in cur: continue

step 5· 탐색과 백트래킹│ │ 중첩

○

cur.append(candidates[i])

○

cur.append(candidates[i]); backtrack(cur, i, target - candidates[i]); cur.pop()

○

cur.append(candidates[i]); backtrack(cur, i + 1, target - candidates[i])

step 6· 재귀 시작

○

backtrack([], 0, target)

○

backtrack([], 1, target)

○

backtrack([candidates[0]], 1, target - candidates[0])

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

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

문제풀이 · 트레이스

· solve

solution.py

class Solution:

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

        candidates.sort()

        res = []

        def backtrack(cur, pos, target):

            if target == 0:

                res.append(cur.copy())

                return

            if target <= 0:

                return

            prev = -1

            for i in range(pos, len(candidates)):

                if candidates[i] == prev:

                    continue

                cur.append(candidates[i])

                backtrack(cur, i + 1, target - candidates[i])

                cur.pop()

                prev = candidates[i]

        backtrack([], 0, target)

        return res

머릿속 dry-run 케이스

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

case 1

[10,1,2,7,6,1,5]
8

→

[[1,1,6],[1,2,5],[1,7],[2,6]]

case 2

[2,5,2,1,2]
5

→

[[1,2,2],[5]]

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