Single-Use Combination Sum

1. Step 1: Initialize Solution.combinationSum2

   Replace the empty starter with the first real state owned by Solution.combinationSum2. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. 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.

3. Step 3: Pass the No Solution case

   Complete the readable core algorithm for one representative Interview case. Sort and skip equal candidates only when they compete at the same recursion depth.

4. Step 4: Harden the Duplicate Input boundary

   Repair the reviewed boundary and pass the complete submission contract. Advancing the index uses each position at most once. At a fixed depth, equal values create identical suffix searches, so skipping later copies removes duplicates while copies at deeper levels remain available.

• Skipping every repeated value globally would remove combinations that legitimately contain two copies.
• recursion and backtracking

• LeetCode 40 — Combination Sum II
• Hello Interview — Backtracking Overview

• 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 two as a complete Interview Problem.

Sort candidates, recurse from the next index after each choice, and skip equal values following the first candidate at each depth.

Why it works: Advancing the index uses each position at most once. At a fixed depth, equal values create identical suffix searches, so skipping later copies removes duplicates while copies at deeper levels remain available.

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

• Reusable-Candidate Combination Sum(opens in a new tab)