DSA-122 · FOCUSED PRACTICE

Combination Sum — Reusable Candidates

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1048 deterministic checks. Learner drafts are not executed.

Understand the problem

Return every unique combination of the distinct positive candidates in nums whose sum is target. A candidate may be reused any number of times; ordering the same selected values differently does not create a new answer.

nums is nonnull, has at most 16 distinct strictly positive int values, and target is in 0..40. Null throws NullPointerException; excess length, zero/negative values, duplicate candidates or an out-of-range target throws IllegalArgumentException before enumeration. These enforced bounds keep recursion and full materialization finite and reviewable.
combinationSum returns nondecreasing rows in numeric lexicographic order. target zero returns [[]], including with empty candidates. Positive target with no feasible combination returns []. A candidate can be Integer.MAX_VALUE; values larger than the current remaining sum are skipped through a sorted suffix break.
Preserve nums exactly, including its original order. Sort only a private clone. Return a fresh mutable outer list and independent mutable result rows; emitting the working path by reference is forbidden. Results from separate calls must share no mutable containers. Integer values are immutable, so sharing boxed values is harmless. Validation is complete even when target is zero; malformed candidates do not become valid because the empty combination would work.

Examples

Input: nums=[7,2,3,6], target=7
Output: [[2,2,3],[7]]
The same 2 may be reused, but [3,2,2] is only a reordering of an existing combination.
Input: nums=[], target=0
Output: [[]]
The empty combination sums to zero.
Input: nums=[4,6], target=5
Output: []
No choice sequence can make the target.

Before you start

Combination paths versus ordered permutations
A strictly decreasing measure for recursive termination

Recognize the structure

This is enumeration of all feasible multisets, not minimum coin count or ordered composition count. A start frontier prevents reordered duplicates. Reuse means a child may choose the same index again; strict positivity makes remaining sum decrease even though that index frontier does not advance. Both parts are needed for correctness and termination.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 210/20,000 characters

Self-review

Can I prove both nondecreasing choice order and strictly decreasing remaining sum?Can I explain exactly why the child frontier is i here?Can I distinguish reusable enumeration, ordered compositions, and minimum coin count?

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

A combination has one sorted value sequence; use a start frontier to enforce it.

Hint 2

Reusing the current index is safe only if another measure decreases.

Hint 3

Track remaining sum, recurse from i, break on sorted overshoot, and undo after each child.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Choose a quantity for each candidate value

Sort a private clone. At candidate index j, enumerate counts from zero through remaining/a[j], then recurse to j+1. At the end of the candidate list, emit a copied path only if the remaining sum is zero. Sort completed rows lexicographically. This compiling baseline has a different recursion coordinate: it fixes how many copies of a value to use instead of choosing the next value repeatedly.

Improve the baseline

Define a frame by frontier and remaining sum

At entry, the nondecreasing path sums to target−remaining, and all future choices must have index at least start. Copy a path when remaining==0 and stop that frame: strictly positive additions cannot preserve a zero remainder.

Allow the chosen index to remain available

Try sorted candidate i, append it, and recurse from i with remaining−a[i]. Moving to i+1 would turn the problem into single-use combinations. Keeping i permits repeated copies without allowing a later return to an earlier value and thus avoids reorderings.

Prune sorted overshoots and restore the path

If a[i]>remaining, break: every later candidate is at least as large. Subtract only an eligible positive int, so the new remaining sum stays nonnegative and no addition can overflow. After the child returns remove exactly the value just chosen, preserving every emitted snapshot.

Why it is correct

Sound sums and canonical order

The empty path has sum zero. Each extension subtracts exactly the appended positive value from remaining, maintaining the sum invariant. Nondecreasing chosen indices make the value row nondecreasing. A zero-remainder emission therefore has the correct target sum and valid reusable candidates.

Completeness and uniqueness

Every feasible multiset has one nondecreasing value sequence because candidates are distinct. The root can choose its first value; each child frontier still permits its next equal or larger value. No feasible suffix is lost by the overshoot break. Conversely only that sorted sequence represents the multiset, so it is emitted once.

Termination and safe pruning

Every descent reduces remaining by at least one. With target≤40, depth is at most 40. Zero would remove this progress argument and a negative candidate could increase remaining, hence both are rejected. For a sorted suffix above remaining, positivity prevents any completion; target zero has exactly the empty additional choice.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static int[] sorted(int[] nums) {
        Objects.requireNonNull(nums,"nums");if(nums.length>16)throw new IllegalArgumentException("materialization limit");
        int[] a=nums.clone();Arrays.sort(a);for(int value:a)if(value<=0)throw new IllegalArgumentException("positive candidates required");for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct candidates required");return a;
    }
    private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
    private static void search(int[] a,int start,int remaining,List<Integer> path,List<List<Integer>> result) {
        if(remaining==0){result.add(new ArrayList<>(path));return;}
        for(int i=start;i<a.length;i++) {
            if(a[i]>remaining)break;
            path.add(a[i]);
            search(a,i,remaining-a[i],path,result);
            path.removeLast();
        }
    }
    public static List<List<Integer>> combinationSum(int[] nums,int target) {
        int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");
        List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
    }
    private static void quantities(int[] a,int at,int remaining,List<Integer> path,List<List<Integer>> result) {
        if(at==a.length){if(remaining==0)result.add(new ArrayList<>(path));return;}
        int before=path.size(),limit=remaining/a[at];for(int count=0;count<=limit;count++){quantities(a,at+1,remaining-count*a[at],path,result);if(count<limit)path.add(a[at]);}while(path.size()>before)path.removeLast();
    }
    public static List<List<Integer>> baseline(int[] nums,int target) {
        int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");List<List<Integer>> result=new ArrayList<>();quantities(a,0,target,new ArrayList<>(),result);result.sort(Solution::compare);return result;
    }
}

Read the meaningful blocks

Reuse is an index decision

The child call search(a,i,remaining−a[i],...) expresses reuse. The path is still restored after every child, so reuse is a permission for a later choice, not permanent mutation or a global count that leaks across branches.

Validation precedes easy answers

Even target zero first clones/sorts and validates every candidate. This prevents [0] or duplicate candidates from bypassing the API’s domain rules. MAX-valued candidates are valid positive inputs, but cannot fit the bounded remaining sum.

Do not sum growing paths in int

The implementation tracks a bounded remaining resource rather than repeatedly summing a potentially long list. The quantity baseline’s count is bounded by remaining/a[j], so count*a[j] cannot exceed remaining and its int arithmetic is also safe under this contract.

Complexity

Let n be candidate count, L=floor(target/minCandidate) for nonempty input, T the number of visited choice-prefix frames, K result rows, and S their total entries. Main time is O(n log(n+1)+nT+S+1); sorted copy, path and recursion require O(n+L+1) auxiliary space, and returned storage is Θ(K+S). A loose bound T≤∑(n^d), d=0..L, shows the potentially exponential search. Empty candidates use one frame.

For the quantity baseline let B be its visited candidate/count states. A safe bound including path maintenance and final ordering is O(n log(n+1)+(L+1)B+S+(L+1)K log(K+1)+1) time, with O(n+L+K+1) auxiliary space including Java object-sort workspace and the same output. The two enumerators organize work differently; neither avoids the cost of returning every combination. Bounds count copying rather than only recursive calls.

Exact-state walkthroughs

Reveal normal and boundary traces

Repeated choices shrink the remaining sum

Input: {"nums":[3,2],"target":6} · Reusable target combinations: [[2,2,2],[3,3]]

Step 1 of 33: Sort a private copy and initialize an empty choice path.

Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.

Reusable combinations — frontier and remaining sum

Phase: initial.

Original input: {"nums":[3,2],"target":6}. Only the private sorted copy is used for ordered choices.

Target: 6. Reuse keeps the chosen index available and decreases the positive remaining sum.

Sorted occurrence positions — equal values still have separate supply

index 0: 2not chosen on path
index 1: 3not chosen on path

Working path — snapshots are copied only at valid emission points

Empty.

Independent rows emitted so far: 0

Empty.

Only zero-remainder paths are emitted. Empty row [] means one valid empty answer; no rows means no answer has been emitted.

Logical recursive frames — root → active leaf, including suspended loop work

Empty.

These frame cards explain Java call-stack state; the implementation does not store a second history. Choose, child entry/return, and undo are distinct steps. Full state tables and static traces appear below; teaching snapshots are excluded from Java workspace costs.

State after this step
Variable	Value
input	`{"nums":[3,2],"target":6}`
sorted	`[2,3]`
path	`[]`
chosenIndices	`[]`
used	`[false,false]`
frames	`[]`
rows	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static int[] sorted(int[] nums) {
 4         Objects.requireNonNull(nums,"nums");if(nums.length>16)throw new IllegalArgumentException("materialization limit");
 5         int[] a=nums.clone();Arrays.sort(a);for(int value:a)if(value<=0)throw new IllegalArgumentException("positive candidates required");for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct candidates required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,int start,int remaining,List<Integer> path,List<List<Integer>> result) {
 9         if(remaining==0){result.add(new ArrayList<>(path));return;}
10         for(int i=start;i<a.length;i++) {
11             if(a[i]>remaining)break;
12             path.add(a[i]);
13             search(a,i,remaining-a[i],path,result);
14             path.removeLast();
15         }
16     }
17     public static List<List<Integer>> combinationSum(int[] nums,int target) {
18         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");
19         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
20     }
21     private static void quantities(int[] a,int at,int remaining,List<Integer> path,List<List<Integer>> result) {
22         if(at==a.length){if(remaining==0)result.add(new ArrayList<>(path));return;}
23         int before=path.size(),limit=remaining/a[at];for(int count=0;count<=limit;count++){quantities(a,at+1,remaining-count*a[at],path,result);if(count<limit)path.add(a[at]);}while(path.size()>before)path.removeLast();
24     }
25     public static List<List<Integer>> baseline(int[] nums,int target) {
26         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");List<List<Integer>> result=new ArrayList<>();quantities(a,0,target,new ArrayList<>(),result);result.sort(Solution::compare);return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a private copy and initialize an empty choice path.
Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[]
phase
"initial"
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":0,"choice":null}]
rows
[]
phase
"enter"
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0}]
rows
[]
phase
"choose"
candidate
0
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":0,"choice":null}]
rows
[]
phase
"enter"
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2]
chosenIndices
[0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0}]
rows
[]
phase
"choose"
candidate
0
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2]
chosenIndices
[0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":0,"choice":null}]
rows
[]
phase
"enter"
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2,2]
chosenIndices
[0,0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":1,"choice":0}]
rows
[]
phase
"choose"
candidate
0
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2,2]
chosenIndices
[0,0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":1,"choice":0},{"start":0,"remaining":0,"next":0,"choice":null}]
rows
[]
phase
"enter"
Copy this valid path into an independent output row.
Subsets emit at every entry. Permutations emit only at full length; combinations emit only at remaining zero. The empty path is one valid result when the contract permits it.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2,2]
chosenIndices
[0,0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":1,"choice":0},{"start":0,"remaining":0,"next":0,"choice":null}]
rows
[[2,2,2]]
phase
"emit"
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2,2]
chosenIndices
[0,0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":1,"choice":0}]
rows
[[2,2,2]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2]
chosenIndices
[0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":1,"choice":null}]
rows
[[2,2,2]]
phase
"undo"
candidate
0
Sorted positive candidates make this whole suffix too large.
Every later value is at least this one, so none can fit the remaining sum. No subtraction or path mutation occurs for the pruned suffix.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2]
chosenIndices
[0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0},{"start":0,"remaining":2,"next":2,"choice":null}]
rows
[[2,2,2]]
phase
"prune"
candidate
1
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,2]
chosenIndices
[0,0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":0}]
rows
[[2,2,2]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":1,"choice":null}]
rows
[[2,2,2]]
phase
"undo"
candidate
0
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,3]
chosenIndices
[0,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":2,"choice":1}]
rows
[[2,2,2]]
phase
"choose"
candidate
1
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,3]
chosenIndices
[0,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":2,"choice":1},{"start":1,"remaining":1,"next":1,"choice":null}]
rows
[[2,2,2]]
phase
"enter"
Sorted positive candidates make this whole suffix too large.
Every later value is at least this one, so none can fit the remaining sum. No subtraction or path mutation occurs for the pruned suffix.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,3]
chosenIndices
[0,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":2,"choice":1},{"start":1,"remaining":1,"next":2,"choice":null}]
rows
[[2,2,2]]
phase
"prune"
candidate
1
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2,3]
chosenIndices
[0,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":2,"choice":1}]
rows
[[2,2,2]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0},{"start":0,"remaining":4,"next":2,"choice":null}]
rows
[[2,2,2]]
phase
"undo"
candidate
1
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":0}]
rows
[[2,2,2]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":1,"choice":null}]
rows
[[2,2,2]]
phase
"undo"
candidate
0
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3]
chosenIndices
[1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1}]
rows
[[2,2,2]]
phase
"choose"
candidate
1
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3]
chosenIndices
[1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1},{"start":1,"remaining":3,"next":1,"choice":null}]
rows
[[2,2,2]]
phase
"enter"
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3,3]
chosenIndices
[1,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1},{"start":1,"remaining":3,"next":2,"choice":1}]
rows
[[2,2,2]]
phase
"choose"
candidate
1
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3,3]
chosenIndices
[1,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1},{"start":1,"remaining":3,"next":2,"choice":1},{"start":1,"remaining":0,"next":1,"choice":null}]
rows
[[2,2,2]]
phase
"enter"
Copy this valid path into an independent output row.
Subsets emit at every entry. Permutations emit only at full length; combinations emit only at remaining zero. The empty path is one valid result when the contract permits it.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3,3]
chosenIndices
[1,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1},{"start":1,"remaining":3,"next":2,"choice":1},{"start":1,"remaining":0,"next":1,"choice":null}]
rows
[[2,2,2],[3,3]]
phase
"emit"
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3,3]
chosenIndices
[1,1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1},{"start":1,"remaining":3,"next":2,"choice":1}]
rows
[[2,2,2],[3,3]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3]
chosenIndices
[1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1},{"start":1,"remaining":3,"next":2,"choice":null}]
rows
[[2,2,2],[3,3]]
phase
"undo"
candidate
1
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[3]
chosenIndices
[1]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":1}]
rows
[[2,2,2],[3,3]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":6,"next":2,"choice":null}]
rows
[[2,2,2],[3,3]]
phase
"undo"
candidate
1
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[[2,2,2],[3,3]]
phase
"leave"
Return the fully materialized, independent rows.
All working choices are restored. Output size and row copying are unavoidable costs; pruning removes duplicate or impossible branches, not the cost of returning every valid answer.
input
{"nums":[3,2],"target":6}
sorted
[2,3]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[[2,2,2],[3,3]]
phase
"complete"
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
[[2,2,2],[3,3]]

An oversized suffix is pruned

Input: {"nums":[2,7],"target":3} · Reusable target combinations: []

Step 1 of 11: Sort a private copy and initialize an empty choice path.

Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.

Reusable combinations — frontier and remaining sum

Phase: initial.

Original input: {"nums":[2,7],"target":3}. Only the private sorted copy is used for ordered choices.

Target: 3. Reuse keeps the chosen index available and decreases the positive remaining sum.

Sorted occurrence positions — equal values still have separate supply

index 0: 2not chosen on path
index 1: 7not chosen on path

Working path — snapshots are copied only at valid emission points

Empty.

Independent rows emitted so far: 0

Empty.

Only zero-remainder paths are emitted. Empty row [] means one valid empty answer; no rows means no answer has been emitted.

Logical recursive frames — root → active leaf, including suspended loop work

Empty.

State after this step
Variable	Value
input	`{"nums":[2,7],"target":3}`
sorted	`[2,7]`
path	`[]`
chosenIndices	`[]`
used	`[false,false]`
frames	`[]`
rows	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static int[] sorted(int[] nums) {
 4         Objects.requireNonNull(nums,"nums");if(nums.length>16)throw new IllegalArgumentException("materialization limit");
 5         int[] a=nums.clone();Arrays.sort(a);for(int value:a)if(value<=0)throw new IllegalArgumentException("positive candidates required");for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct candidates required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,int start,int remaining,List<Integer> path,List<List<Integer>> result) {
 9         if(remaining==0){result.add(new ArrayList<>(path));return;}
10         for(int i=start;i<a.length;i++) {
11             if(a[i]>remaining)break;
12             path.add(a[i]);
13             search(a,i,remaining-a[i],path,result);
14             path.removeLast();
15         }
16     }
17     public static List<List<Integer>> combinationSum(int[] nums,int target) {
18         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");
19         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
20     }
21     private static void quantities(int[] a,int at,int remaining,List<Integer> path,List<List<Integer>> result) {
22         if(at==a.length){if(remaining==0)result.add(new ArrayList<>(path));return;}
23         int before=path.size(),limit=remaining/a[at];for(int count=0;count<=limit;count++){quantities(a,at+1,remaining-count*a[at],path,result);if(count<limit)path.add(a[at]);}while(path.size()>before)path.removeLast();
24     }
25     public static List<List<Integer>> baseline(int[] nums,int target) {
26         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");List<List<Integer>> result=new ArrayList<>();quantities(a,0,target,new ArrayList<>(),result);result.sort(Solution::compare);return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a private copy and initialize an empty choice path.
Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[]
phase
"initial"
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":0,"choice":null}]
rows
[]
phase
"enter"
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0}]
rows
[]
phase
"choose"
candidate
0
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":0,"remaining":1,"next":0,"choice":null}]
rows
[]
phase
"enter"
Sorted positive candidates make this whole suffix too large.
Every later value is at least this one, so none can fit the remaining sum. No subtraction or path mutation occurs for the pruned suffix.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":0,"remaining":1,"next":1,"choice":null}]
rows
[]
phase
"prune"
candidate
0
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[2]
chosenIndices
[0]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0}]
rows
[]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":null}]
rows
[]
phase
"undo"
candidate
0
Sorted positive candidates make this whole suffix too large.
Every later value is at least this one, so none can fit the remaining sum. No subtraction or path mutation occurs for the pruned suffix.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":3,"next":2,"choice":null}]
rows
[]
phase
"prune"
candidate
1
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[]
phase
"leave"
Return the fully materialized, independent rows.
All working choices are restored. Output size and row copying are unavoidable costs; pruning removes duplicate or impossible branches, not the cost of returning every valid answer.
input
{"nums":[2,7],"target":3}
sorted
[2,7]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[]
phase
"complete"
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
[]

Zero target emits the empty combination

Input: {"nums":[],"target":0} · Reusable target combinations: [[]]

Step 1 of 6: Sort a private copy and initialize an empty choice path.

Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.

Reusable combinations — frontier and remaining sum

Phase: initial.

Original input: {"nums":[],"target":0}. Only the private sorted copy is used for ordered choices.

Target: 0. Reuse keeps the chosen index available and decreases the positive remaining sum.

Sorted occurrence positions — equal values still have separate supply

Working path — snapshots are copied only at valid emission points

Empty.

Independent rows emitted so far: 0

Empty.

Only zero-remainder paths are emitted. Empty row [] means one valid empty answer; no rows means no answer has been emitted.

Logical recursive frames — root → active leaf, including suspended loop work

Empty.

State after this step
Variable	Value
input	`{"nums":[],"target":0}`
sorted	`[]`
path	`[]`
chosenIndices	`[]`
used	`[]`
frames	`[]`
rows	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static int[] sorted(int[] nums) {
 4         Objects.requireNonNull(nums,"nums");if(nums.length>16)throw new IllegalArgumentException("materialization limit");
 5         int[] a=nums.clone();Arrays.sort(a);for(int value:a)if(value<=0)throw new IllegalArgumentException("positive candidates required");for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct candidates required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,int start,int remaining,List<Integer> path,List<List<Integer>> result) {
 9         if(remaining==0){result.add(new ArrayList<>(path));return;}
10         for(int i=start;i<a.length;i++) {
11             if(a[i]>remaining)break;
12             path.add(a[i]);
13             search(a,i,remaining-a[i],path,result);
14             path.removeLast();
15         }
16     }
17     public static List<List<Integer>> combinationSum(int[] nums,int target) {
18         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");
19         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
20     }
21     private static void quantities(int[] a,int at,int remaining,List<Integer> path,List<List<Integer>> result) {
22         if(at==a.length){if(remaining==0)result.add(new ArrayList<>(path));return;}
23         int before=path.size(),limit=remaining/a[at];for(int count=0;count<=limit;count++){quantities(a,at+1,remaining-count*a[at],path,result);if(count<limit)path.add(a[at]);}while(path.size()>before)path.removeLast();
24     }
25     public static List<List<Integer>> baseline(int[] nums,int target) {
26         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");List<List<Integer>> result=new ArrayList<>();quantities(a,0,target,new ArrayList<>(),result);result.sort(Solution::compare);return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a private copy and initialize an empty choice path.
Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.
input
{"nums":[],"target":0}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[]
rows
[]
phase
"initial"
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[],"target":0}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[{"start":0,"remaining":0,"next":0,"choice":null}]
rows
[]
phase
"enter"
Copy this valid path into an independent output row.
Subsets emit at every entry. Permutations emit only at full length; combinations emit only at remaining zero. The empty path is one valid result when the contract permits it.
input
{"nums":[],"target":0}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[{"start":0,"remaining":0,"next":0,"choice":null}]
rows
[[]]
phase
"emit"
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[],"target":0}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[]
rows
[[]]
phase
"leave"
Return the fully materialized, independent rows.
All working choices are restored. Output size and row copying are unavoidable costs; pruning removes duplicate or impossible branches, not the cost of returning every valid answer.
input
{"nums":[],"target":0}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[]
rows
[[]]
phase
"complete"
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
[[]]

No candidates for a positive target

Input: {"nums":[],"target":4} · Reusable target combinations: []

Step 1 of 5: Sort a private copy and initialize an empty choice path.

Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.

Reusable combinations — frontier and remaining sum

Phase: initial.

Original input: {"nums":[],"target":4}. Only the private sorted copy is used for ordered choices.

Target: 4. Reuse keeps the chosen index available and decreases the positive remaining sum.

Sorted occurrence positions — equal values still have separate supply

Working path — snapshots are copied only at valid emission points

Empty.

Independent rows emitted so far: 0

Empty.

Only zero-remainder paths are emitted. Empty row [] means one valid empty answer; no rows means no answer has been emitted.

Logical recursive frames — root → active leaf, including suspended loop work

Empty.

State after this step
Variable	Value
input	`{"nums":[],"target":4}`
sorted	`[]`
path	`[]`
chosenIndices	`[]`
used	`[]`
frames	`[]`
rows	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static int[] sorted(int[] nums) {
 4         Objects.requireNonNull(nums,"nums");if(nums.length>16)throw new IllegalArgumentException("materialization limit");
 5         int[] a=nums.clone();Arrays.sort(a);for(int value:a)if(value<=0)throw new IllegalArgumentException("positive candidates required");for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct candidates required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,int start,int remaining,List<Integer> path,List<List<Integer>> result) {
 9         if(remaining==0){result.add(new ArrayList<>(path));return;}
10         for(int i=start;i<a.length;i++) {
11             if(a[i]>remaining)break;
12             path.add(a[i]);
13             search(a,i,remaining-a[i],path,result);
14             path.removeLast();
15         }
16     }
17     public static List<List<Integer>> combinationSum(int[] nums,int target) {
18         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");
19         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
20     }
21     private static void quantities(int[] a,int at,int remaining,List<Integer> path,List<List<Integer>> result) {
22         if(at==a.length){if(remaining==0)result.add(new ArrayList<>(path));return;}
23         int before=path.size(),limit=remaining/a[at];for(int count=0;count<=limit;count++){quantities(a,at+1,remaining-count*a[at],path,result);if(count<limit)path.add(a[at]);}while(path.size()>before)path.removeLast();
24     }
25     public static List<List<Integer>> baseline(int[] nums,int target) {
26         int[] a=sorted(nums);if(target<0||target>40)throw new IllegalArgumentException("invalid target");List<List<Integer>> result=new ArrayList<>();quantities(a,0,target,new ArrayList<>(),result);result.sort(Solution::compare);return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a private copy and initialize an empty choice path.
Caller input order and values are preserved. Paths and results own separate containers. Sorted positions distinguish equal occurrences even though the output contains values.
input
{"nums":[],"target":4}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[]
rows
[]
phase
"initial"
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
{"nums":[],"target":4}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[{"start":0,"remaining":4,"next":0,"choice":null}]
rows
[]
phase
"enter"
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
{"nums":[],"target":4}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[]
rows
[]
phase
"leave"
Return the fully materialized, independent rows.
All working choices are restored. Output size and row copying are unavoidable costs; pruning removes duplicate or impossible branches, not the cost of returning every valid answer.
input
{"nums":[],"target":4}
sorted
[]
path
[]
chosenIndices
[]
used
[]
frames
[]
rows
[]
phase
"complete"
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
[]

Test the contract

Input: Empty candidates with targets zero and positive
Output: [[]] / []
Separates one empty solution from no solution.
Input: A single candidate 1 with target 40
Output: one forty-entry row
Exercises the depth bound.
Input: Every subset of denominations 1..5 and targets 0..15
Output: matches amount-layer set DP
Independent checking canonicalizes combinations generated through different last additions.
Input: MAX candidate alongside small usable values
Output: only fitting combinations
Overshoot checks avoid unsafe subtraction.
Input: Zero, negative, duplicate, too many candidates or invalid target
Output: documented exception
Validation still runs for target zero.

Common mistakes and counterexamples

Advance to i+1 after every choice

Counterexample: [2], target 4 must return [2,2].

Recurse from i when reuse is allowed.

Restart from zero after every choice

Counterexample: [2,3], target 5 generates both [2,3] and [3,2].

Keep a nondecreasing index frontier.

Accept zero or negative candidates

Counterexample: Zero can recurse with the same remaining sum forever.

Reject nonpositive values and prove remaining decreases.

Return on the first valid combination

Counterexample: [2,3,7], target 7 has both [2,2,3] and [7].

Emit a snapshot, return only from that frame, then continue parent siblings.

Follow-ups

Count combinations instead of listing them.

Use coin-oriented DP with candidate types outside and increasing sum inside for unlimited reuse. State what each table entry counts; sum-oriented transitions can instead count ordered compositions. Counting avoids storing K rows.

Permit duplicate candidate values.

Define them as equivalent reusable denominations, then normalize a sorted copy to distinct values or apply a sound sibling policy. Treating duplicate occurrences as different reusable types creates duplicate value combinations.

Allow zero or negative candidates.

The finite-enumeration contract must change: zero adds arbitrarily many equivalent-length extensions and opposite signs can yield infinitely many solutions. Add an explicit length/count limit before choosing a termination proof and state representation.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform parity claims.