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

Combination Sum II – Solution & Complexity

Interview solutions
/
Combination Sum II

Solution Walkthrough

  1. Step 1: Recognize the once-only search space

    • This is backtracking over indices, not over unlimited value reuse: once you take candidates[i], the next recursive call must continue from i + 1.
    • Duplicate values in the input are the real twist. If two equal numbers sit next to each other in the sorted array, starting a branch from both of them at the same recursion depth would create duplicate combinations.
    • Sorting first gives you both pieces you need: deterministic canonical order and an easy adjacent-value check for duplicate skipping.

  2. Step 2: Baseline backtracking with same-level duplicate skipping

    • Sort the array, keep a path, and let each call choose the next index from start onward.
    • When remaining == 0, record the current path immediately; that DFS discovery order is the required outer-list order.
    • At a given recursion depth, skip candidates[i] when i > start and it matches candidates[i - 1]. That preserves one representative branch per equal-value run at that level.
    • This baseline is fully correct, but it may still recurse into branches that already overshoot the target.
    def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    if target <= 0:
        return []

    candidates = sorted(candidates)
    answer: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            answer.append(path.copy())
            return
        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return answer

  3. Step 3: Add sorted-array pruning

    • After sorting, once candidates[i] is already larger than the remaining target, every later value is also too large.
    • That means the current loop can break immediately instead of recursing into guaranteed failures.
    • This optimization preserves the exact same canonical output order because it only removes branches that could never produce a valid combination.

  4. Step 4: Final optimized solution and complexity

    The algorithm sorts once, then backtracks left-to-right while skipping equal values at the same depth and breaking when the next candidate is too large. In the worst case it explores subset-style branches, so the time complexity is O(n * 2^n) and the extra recursion/path space is O(n) (excluding the returned output).

    def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    if target <= 0:
        return []

    candidates = sorted(candidates)
    answer: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            answer.append(path.copy())
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return answer

  5. Step 5: Common mistakes to watch for

    • Reusing the same index by recursing with i instead of i + 1, which accidentally turns the problem back into Combination Sum I.
    • Skipping every duplicate globally instead of only duplicates at the same recursion depth. You still need to allow [1,1,6] when two separate 1 entries exist.
    • Sorting after backtracking or post-sorting the output, which can hide ordering bugs instead of producing the required canonical DFS order directly.

FAQ

See also

Practice Combination Sum II online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Combination Sum solution (medium)H-Index solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?