Reusable-Candidate Combination Sum

Interview Problem Interview Medium Constraint Satisfaction Array Backtracking

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.combinationSum(candidates, target). Candidates are distinct positive integers and may be selected repeatedly. Return every unique combination totaling target; output order does not matter.

Starter code

class Solution:
    def combinationSum(self, candidates, target):
        pass

Test cases

reuse-required

{
  "args": [
    [
      2,
      3,
      6,
      7
    ],
    7
  ]
}

Expected: [[2,2,3],[7]]

Wizard outline

Step 1: Initialize Solution.combinationSum
Replace the empty starter with the first real state owned by Solution.combinationSum. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the No Solution case
Complete the readable core algorithm for one representative Interview case. Use a start index to prevent reordered duplicates while allowing reuse of the current candidate.
Step 4: Harden the Reuse Required boundary
Repair the reviewed boundary and pass the complete submission contract. Every path is nondecreasing, so no value multiset is emitted in another order; retaining i permits every legal reuse count, and remainder zero emits exactly the target combinations.

Footguns and prerequisites

Recurse with the same index after choosing a reusable candidate, not index + 1.
recursion and backtracking

Reviewed references

Practice prerequisites

Complete One Backtracking Frame(opens in a new tab)
Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing combination sum as a complete Interview Problem.

Recommended approach and implementation

Backtrack over nondecreasing candidate indices; after choosing candidates[i], recurse from i with a smaller remainder.

Why it works: Every path is nondecreasing, so no value multiset is emitted in another order; retaining i permits every legal reuse count, and remainder zero emits exactly the target combinations.

class Solution:
    def combinationSum(self, candidates, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        result = []
        path = []
        def backtrack(start, remaining):
            if remaining == 0:
                result.append(path[:])
                return
            for index in range(start, len(candidates)):
                value = candidates[index]
                if value > remaining:
                    continue
                path.append(value)
                backtrack(index, remaining - value)
                path.pop()
        backtrack(0, target)
        return result

Similar exercises

Single-Use Combination Sum(opens in a new tab)