intermediate10 min read·Updated October 3, 2026

Combination Sum Explained: Tracing [2, 3, 6, 7] for Target 7

Master Combination Sum with unlimited reuse. Follow a complete mental model walkthrough using candidates [2, 3, 6, 7] and target 7 with backtracking.

By Learnisim AI·Published October 3, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic recursion
  • Backtracking fundamentals
  • Array slicing and index pointers
Combination Sum (Unlimited Reuse) — Candidates [2, 3, 6, 7], Target = 7 1. Core Rules & Setup • Candidates: [2, 3, 6, 7] • Target Sum: 7 • Unlimited item reuse allowed • Unique sets only (no [2,3,2]) 2. The Pointer Rule: Stay (i) vs Advance (i+1) Include Candidate & STAY (i) Allows reuse: e.g., pick 2 again next Skip & ADVANCE (i + 1) Abandons value: prevents duplicates 3. Decision Tree Trace for Target = 7 Start: rem=7, [] Choose 2 (rem=5) Skip 2 -> Try 3 Choose 2 (rem=3) Try 3 (rem=2) Valid! [2, 2, 3] rem=-1 (Stop) Try 6 (rem=1) Valid! [7] Final Unique Combinations Found: [[2, 2, 3], [7]]
Candidates [2, 3, 6, 7] target 7 overview diagram
Why

Why standard subsets fail when unlimited item reuse is allowed

Phase 1: The Multi-Choice Puzzle

Imagine you are building a system that must distribute coins to match a exact currency total, or packing items into a container where identical parts can be picked over and over. You are given the candidate set [2, 3, 6, 7] and your goal is to find all unique combinations that sum up to a target of 7. Unlike standard subset problems where each element is consumed once and discarded, the rules here state that any number from the array can be chosen an unlimited number of times.
Without a structured search strategy, this freedom quickly turns into chaos. If you try to generate combinations by blindly picking items until you hit or exceed 7, you will inevitably generate duplicate sets like [2, 2, 3] and [3, 2, 2], or get stuck in infinite recursive loops because you forgot to track what remains of your target.
To make matters worse, the output must be unique: order does not matter, meaning [2, 2, 3] and [3, 2, 2] represent the exact same collection of numbers and only one should appear in your final result. Before we write any search logic or recursion trees, we need to understand why naive enumeration breaks down and how constraining our choices prevents redundant work.
python
candidates = [2, 3, 6, 7]
target = 7
# Why does allowing unlimited reuse of these numbers
# cause standard power-set algorithms to fail?
Combination Sum: Why Standard Subsets Fail with Unlimited Reuse Candidates: [2, 3, 6, 7] • Target: 7 • Goal: Find unique combinations without duplicate permutations Standard Subset Approach (Consumes Items) • Each item used at most once (Power Set) • Result: Missing solutions & cant reuse [2,2,3] Start: [] Pick 2 Pick 3 Why Naive Enumeration Breaks Down: 1. Infinite recursion if element is re-picked blindly 2. Generates duplicate permutations: [2,2,3] & [3,2,2] 3. Misses valid sums because capacity exhausts early Fails Valid Strategy (Unlimited Reuse + State Tracking) • Pass index forward so we never look backward • Allow remaining target to decrease with same item Target: 7 Choice: 2 (rem: 5) Choice: 7 (rem: 0) ✓ Match Found: [7] Reuse 2 (rem: 3) Pick 3 (rem: 0) ✓ Valid: [2, 2, 3] Final Unique Results: • [2, 2, 3] (using index i=0) • [3, 2, 2] avoided via index rule • [7] (exact target) VS
Why standard subsets fail when unlimited item reuse is allowed diagram
Model

The Unlimited-Reuse Decision Tree and Index Pointer Model

Phase 2: The Decision Tree Model

To make sense of how elements can repeat without spiraling into infinite loops or duplicate combinations, we need a mental model of navigation. For our running example, we are given candidates = [2, 3, 6, 7] and target = 7. We can picture this search as exploring a branching decision tree from top to bottom.
At each node in this tree, we stand at a specific start index in our candidates array and possess a remaining amount of our target, called remain. We have two structural choices for every candidate we consider:
1. Include the candidate at the current index, subtract its value from remain, and stay at that exact same index because we are allowed unlimited reuse.
2.Skip the candidate by moving our pointer forward to the next index, abandoning any further reuse of that specific value.
This exact rule—recursing on i instead of i + 1—is what separates a standard subset problem from combination sum. If we moved to i + 1 immediately, we could never form [2, 2, 3] because once we picked 2, we would be banned from picking it again. By staying at index 0 after choosing 2, our next branch is still allowed to look at 2.
Start: remain = 7, path = []
├── Choose 2 -> remain = 5, path = [2]
│ ├── Choose 2 -> remain = 3, path = [2, 2]
│ │ ├── Choose 2 -> remain = 1, path = [2, 2, 2]
│ │ │ ├── Choose 2 -> remain = -1 (Invalid, stop)
│ │ │ └── Choose 3 -> remain = -2 (Invalid, stop)
│ │ └── Choose 3 -> remain = 0 (Valid! Found [2, 2, 3])
To prevent counting duplicate combinations like [2, 3, 2] or [3, 2, 2], the pointer only moves forward when we permanently abandon a candidate. We never look backward in the array. This strict directional discipline ensures every unique combination of numbers appears in exactly one ordered branch of the tree.
Combination Sum: Unlimited-Reuse Decision Tree (Candidates: [2, 3, 6, 7] | Target: 7) Rule: Stay at index i to reuse element (remain >= 0); move to i+1 only when abandoning. Candidates & Pointer Index i=0 2 i=1 3 i=2 6 i=3 7 Reuse (stay at i) vs Advance (i+1) Core Mechanics 1. Include & Stay (Reuse) remain -= val | recurse(i) 2. Skip & Advance abandon val | recurse(i + 1) 3. Base Conditions remain == 0 (Valid) | remain < 0 (Stop) Decision Tree Explorer (Target = 7) Choose 2 +2 (stay) Skip 2 (i+1) +2 (stay) Choose 3 +2 +3 Start: remain=7, [] remain=5, path=[2] remain=3, [2, 2] remain=4, path=[3] remain=1, [2,2,2] remain=0, [2,2,3] ✓ remain=-1 (Stop) Found! Target Met Uniqueness guarantee: Pointer never moves backward; duplicates like [3, 2, 2] are naturally avoided.
The Unlimited-Reuse Decision Tree and Index Pointer Model diagram
Worked example

Tracing the Backtracking Search for Candidates 2, 3, 6, 7 and Target 7

Phase 3: Worked example

Now let's trace our decision tree model on our concrete instance: and . We define our recursive function as , where is our current index in the candidates array, is the remaining target sum, and is the list of chosen numbers so far.

Given

- Candidates: [2, 3, 6, 7] (sorted ascending)
•Target: 7

- Expected unique valid combinations: [[2, 2, 3], [7]]

Steps

1. Initial call:
2. Branch 0 (, candidate 2):
- , , recurse (reuse index 0):
- Branch 0 (, candidate 2): , , recurse :
- Branch 0 (, candidate 2): , , recurse :
- Branch 0 (, candidate 2): . Negative! Prune branch.
- Branch 1 (, candidate 3): . Prune branch.
- Branch 1 (, candidate 3): . Valid combination found! Add [2, 2, 3] to results. Unchoose 3.
- Branch 2 (, candidate 6): . Prune branch.
- Branch 1 (, candidate 3): , , recurse :
- Branch 1 (, candidate 3): . Prune branch.
3. Branch 3 (, candidate 7):
- , . Valid combination found! Add [7] to results.

Result

After exhausting all valid branches in our decision tree, our algorithm accumulates exactly [[2, 2, 3], [7]] without generating duplicate permutations like [3, 2, 2].
python
def combinationSum(candidates, target):
    result = []
    candidates.sort()
    
    def backtrack(start, remain, path):
        if remain == 0:
            result.append(list(path))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break
            path.append(candidates[i])
            backtrack(i, remain - candidates[i], path)
            path.pop()
            
    backtrack(0, target, [])
    return result
Backtracking Trace: Candidates [2, 3, 6, 7], Target = 7 backtrack(start, remain, path) Candidates: [2, 3, 6, 7] start=0, remain=7 path = [ ] i=0 (2) i=3 (7) start=0, remain=5 path = [2] remain = 0 ! Found: [7] i=0 (+2) i=1 (+3) start=0, remain=3 path = [2, 2] remain = 2 Branch [2, 3] explored i=1 (remain=0) remain = 0 ! Found: [2, 2, 3] Accumulated Results (Valid Combinations) [[2, 2, 3], [7]] Pruned when candidate > remain or remain < 0 (e.g. [2,2,2,2])
Tracing the Backtracking Search for Candidates 2, 3, 6, 7 and Target 7 diagram
Practice

Predicting the Decision Tree Path for a Modified Target

Phase 4: Practice

Let us test how well you can mentally execute the backtracking decision tree we just traced. Recall our working candidate set is , but suppose we slightly adjust our objective to a target of 5.
Imagine you are at the root of the recursion tree with , , and . You pick the first candidate, 2. Because unlimited reuse is allowed, your recursive call passes again, leaving a of 3. From there, you pick 2 a second time, leaving a of 1. When you inspect candidates at , every single candidate in is strictly greater than 1.
Your task is to mentally step through the unrolling of that dead-end branch and determine the very next valid combination the algorithm discovers after backtracking.

The Practice Task

Given and , what is the second valid combination discovered by the backtracking algorithm (after is rejected, assuming the array is sorted)?
Think through how the index pointer increments from 0 to 1 when the path pops 2 and tries candidate 3.
Try this: candidates = [2, 3, 6, 7], target = 5

Path trace starts at [2], then [2, 2], then fails at remain 1.

Backtrack -> Pop 2 -> Try next index/candidate...

Apply

Applying the Unlimited-Reuse Pattern to a New Target

Phase 5: Applying the Pattern

Now that you have traced candidates for target 7, let's transfer this exact mental model to a new scenario without rebuilding the algorithm. Suppose we keep the identical candidate pool , but we change our goal to .
Recall the two core rules established in our earlier phases: first, sorting the array lets us break early when candidates[i] > remain; second, passing index i instead of i + 1 allows unlimited reuse of the current element. When applying this to target 8, the first successful leaf will exhaust the smallest candidate repeatedly until a match or overshoot occurs.
To test your mastery of this transfer, write down or mentally trace the very first path the recursion explores when starting from start = 0 and remain = 8. Consider which candidate gets added four times before triggering a backtrack, and how the algorithm eventually discovers alternative combinations like and (if 5 were present, but here it must find combinations using only ).
python
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res = []
    
    def backtrack(start: int, remain: int, path: list[int]):
        if remain == 0:
            res.append(list(path))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break
            path.append(candidates[i])
            backtrack(i, remain - candidates[i], path)
            path.pop()
            
    backtrack(0, target, [])
    return res

# Try evaluating: combinationSum([2, 3, 6, 7], 8)

FAQ

How does the working example [2, 3, 6, 7] for target 7 produce [[2, 2, 3], [7]]?
The algorithm explores paths by picking candidates. Choosing [2, 2, 3] totals 7. Choosing 7 directly hits the target. Combinations like [3, 2, 2] are prevented by strictly keeping the index pointer non-decreasing (allowing reuse of the current index i, but never looking backward to i-1).
Why do standard subset backtracking approaches fail when unlimited item reuse is allowed?
Standard subset generators advance the index pointer (i + 1) after every choice to ensure each element is used at most once. For combination sum, you must pass i instead of 𝑖 + 1 into recursive calls so the same element can be chosen again.
How do we prevent duplicate permutations like [2, 2, 3] and [3, 2, 2] in the output?
By enforcing an index-selection rule: when recursing with item reuse, we pass the current index i. For future choices, we only consider elements at index i or greater, guaranteeing that elements are always added in non-decreasing order.
What is the time complexity of the combination sum problem?
The time complexity is O(N^(T/M)), where N is the number of candidates, T is the target value, and M is the minimum value among the candidates. The worst-case shape of the decision tree depends heavily on the target and candidate distribution.

Keep learning