{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Combination Sum – Solution & Complexity

Interview solutions
/
Combination Sum

1. Recognize the Pattern

The key pattern is: Backtracking branches between reusing and skipping each candidate. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(2^(t/m)). Space: O(t/m).

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    answer, current = [], []
    def search(index, remaining):
        if remaining == 0:
            answer.append(current.copy()); return
        if index == len(candidates) or remaining < 0: return
        current.append(candidates[index])
        search(index, remaining - candidates[index])
        current.pop()
        search(index + 1, remaining)
    search(0, target)
    return answer

FAQ

See also

Practice Combination Sum online (run code in the browser)Permutations solution (medium)Subsets solution (medium)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?