Combination Sum

medium · backtracking

candidates contains distinct positive integers. Return combinations summing to target >= 0, reusing a candidate any number of times. Sort values within each combination ascending and return the outer list in Python lexicographic list order; no duplicate combinations. target <= 30 with at most 8 candidates. Target 0 has exactly one combination, []. Examples (JSON; null means Python None): Input: {"candidates": [2, 3, 6, 7], "target": 7} Output: [[2, 2, 3], [7]] Input: {"candidates": [2, 3, 5], "target": 8} Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Starter code

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """Enumerate nondecreasing reusable-candidate combinations."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  2. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.

  3. Me at 2amCharacter joke · No posting date

    I renamed the function and everything broke. The function was load-bearing.

  4. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.