What is the best way to solve Combination Sum?

The optimized O(n) approach using Backtracking patterns is generally preferred.

상위 150개 인터뷰쉬움

조합합

'조합 합계' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

고유한 정수 후보 배열과 목표 정수 목표가 주어지면 선택한 숫자의 합이 목표에 해당하는 모든 고유한 후보 조합 목록을 반환합니다. 어떤 순서로든 조합을 반환할 수 있습니다.

동일한 번호를 후보자 중에서 무제한으로 선택할 수 있습니다. 선택한 숫자 중 하나 이상의 빈도가 다른 경우 두 가지 조합은 고유합니다.

combinationSum(candidates: list, target: int) -> list 함수를 구현하세요.

제약

•1 <= candidates.length <= 30
•2 <= candidates[i] <= 40
•All elements of candidates are distinct
•1 <= target <= 40

예

Example 1

Input

[2,3,6,7], 7

Output

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

Explanation

2 + 2 + 3 = 7 and 7 = 7. These are the only two combinations.

Example 2

Input

[2,3,5], 8

Output

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

Explanation

2+2+2+2 = 8, 2+3+3 = 8, and 3+5 = 8.

Example 3

Input

[2], 1

Output

[]

Explanation

No combination of 2's can sum to 1.

Need a Hint?

세트 또는 힙과 같은 역추적 관련 데이터 구조를 사용하는 것이 좋습니다.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

역추적 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def combination_sum_opt(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    candidates.sort()
    def backtrack(remain, stack, start):
        if remain == 0:
            res.append(list(stack))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain: break
            stack.append(candidates[i])
            backtrack(remain - candidates[i], stack, i)
            stack.pop()
    backtrack(target, [], 0)
    return res

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def combination_sum_brute(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