{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Combination Sum – Solution & Complexity

Interview solutions
/
Combination Sum

Solution Walkthrough

  1. Step 1: Recognize the Pattern

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

  2. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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)Combination Sum II solution (medium)Generate Parentheses solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?