DSA-123 · Single-use combination search with local duplicate pruning and positive-sum bounds

Combination Sum II — Each Candidate Once

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return every distinct nondecreasing value combination summing to target when each input occurrence may be used at most once. Duplicate candidate values are valid, but equivalent value rows must appear only once.

nums is nonnull, contains at most 20 strictly positive int occurrences, and target is any nonnegative int. Null throws NullPointerException; excess length, a nonpositive value or a negative target throws IllegalArgumentException. Repeated values and Integer.MAX_VALUE candidates are valid.
combinationSum returns unique rows in numeric lexicographic order. target zero returns [[]], even for empty nums. Positive target without a feasible selection returns []. Each value’s count in a row is bounded by its count in nums; equivalent choices of equal occurrences are not distinct answers.
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. Validate every candidate before any zero-target return. The full-int target domain is safe because the main method subtracts only fitting positive values; the baseline sums selected values in long.

Examples

Input: nums=[10,1,2,7,6,1,5], target=8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Two available 1 occurrences can both appear, while equal sibling starts are suppressed.
Input: nums=[2], target=4
Output: []
This occurrence can be chosen only once, unlike DSA-122.
Input: nums=[MAX,MAX,1], target=MAX
Output: [[MAX]]
Two equal MAX occurrences represent one singleton answer; their combined sum does not wrap into an int.

Before you start

Sorted duplicate ownership from DSA-119
Remaining-sum search and reusable versus single-use resources

Recognize the structure

Combine two independent restrictions: advancing indices prevents occurrence reuse, and skipping equal siblings prevents duplicate value answers. Positivity allows the same sorted overshoot break as reusable combination sum, but depth is bounded by input length even when the target is huge. Do not normalize away all duplicates, because their multiplicity can be essential.

Try before revealing

Hint 1

Use the same sibling ownership rule as duplicate subsets.

Hint 2

Each chosen occurrence is consumed, so the child begins after it.

Hint 3

Copy at remaining zero; otherwise skip equal siblings, break on overshoot, recurse from i+1, and undo.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate occurrence masks and filter sums

Sort a clone. For every subset mask, construct its selected nondecreasing row and accumulate the sum in long. Keep target-equal rows in a lexicographic TreeSet to remove duplicates. The 20-occurrence limit keeps 1<<n safe. This compiling baseline considers all 2^n occurrence subsets regardless of target feasibility.

Improve the baseline

Maintain a single-use frontier and remaining sum

At entry, path uses strictly increasing sorted occurrence indices and has sum target−remaining. A zero remainder emits a copied row and stops the frame, because all unused values are positive.

Skip equivalent siblings while retaining deeper equal copies

At frame start, skip i>start when a[i]==a[i−1]. The earlier equal sibling already represents all value completions for that first choice. A child may still choose an equal value at its own start, allowing rows such as [1,1,6].

Advance after a fitting occurrence

Break if a[i]>remaining. Otherwise append it and recurse from i+1 with remaining−a[i], then remove it. Advancing the frontier expresses single use; changing it to i silently solves the reusable problem instead.

Why it is correct

Sound resource use and sums

Each child starts after the chosen index, so no occurrence repeats. Remaining equals target minus the path sum and never becomes negative. Emission at zero yields a feasible combination, with sorted values and valid multiplicities.

Complete canonical choices

For any feasible value multiset, choose its earliest eligible sorted occurrences. Each first needed occurrence survives sibling pruning, and no needed fitting value is removed by the overshoot break. Following these canonical choices reaches a zero-remainder emission.

Unique results and bounded depth

At the first differing occurrence choice of two equal value rows, both paths would select the same value in one frame. The later equal sibling is skipped, so both paths cannot survive. Indices strictly increase and depth is at most n, proving termination independently of target magnitude. Positive remaining pruning only removes impossible branches.

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>20)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");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(i>start&&a[i]==a[i-1])continue;
            if(a[i]>remaining)break;
            path.add(a[i]);
            search(a,i+1,remaining-a[i],path,result);
            path.removeLast();
        }
    }
    public static List<List<Integer>> combinationSum(int[] nums,int target) {
        int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");
        List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
    }
    public static List<List<Integer>> baseline(int[] nums,int target) {
        int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");Set<List<Integer>> unique=new TreeSet<>(Solution::compare);
        for(int mask=0;mask<(1<<a.length);mask++){long sum=0;List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0){sum+=a[i];row.add(a[i]);}if(sum==target)unique.add(row);}return new ArrayList<>(unique);
    }
}

Read the meaningful blocks

Single use and deduplication solve different bugs

i+1 prevents selecting one occurrence twice; i>start duplicate suppression prevents different equal occurrences from starting equivalent sibling branches. Removing either guard changes the answer set even when the other remains.

Large sums belong in long in the baseline

Twenty positive int values can sum beyond int. A wrapped int sum could accidentally equal target and emit a false answer. The main method avoids accumulated-sum overflow by subtracting only values≤remaining; the independent subset oracle also uses long.

Keep all available occurrences in the sorted copy

Replacing nums with a set loses legal multiplicities. On [1,1,6], target eight needs both ones. The correct optimization suppresses symmetric search branches rather than deleting supply from the input multiset.

Complexity

Let n be occurrences, T visited canonical prefix states, K emitted rows, and S total output entries. Main time is O(n log(n+1)+nT+S+1), with T≤2^n as a safe bound. Sorted copy, path and recursion need O(n+1) auxiliary space, while output needs Θ(K+S). A huge target does not create huge depth because each index is used at most once.

The mask baseline takes O(n log(n+1)+n2^n(1+log(K+1))+1) time as a safe bound including long summation, row creation and lexicographic TreeSet comparisons. Live storage is O(K+S+n+1), including retained result rows and set nodes; discarded candidate rows do not all remain live. Exact traces deliberately retain history separately from these workspace costs.

Exact-state walkthroughs

Reveal normal and boundary traces

One-use indices coexist with deeper duplicate values

Input: {"nums":[1,1,2],"target":3} · Single-use target combinations: [[1,2]]

Step 1 of 24: 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.

Single-use combinations — occurrence supply and duplicate pruning

Phase: initial.

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

Target: 3. Each occurrence is consumed once; the child frontier advances past its index.

Sorted occurrence positions — equal values still have separate supply

index 0: 1not chosen on path
index 1: 1not chosen on path
index 2: 2not 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":[1,1,2],"target":3}`
sorted	`[1,1,2]`
path	`[]`
chosenIndices	`[]`
used	`[false,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>20)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");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(i>start&&a[i]==a[i-1])continue;
12             if(a[i]>remaining)break;
13             path.add(a[i]);
14             search(a,i+1,remaining-a[i],path,result);
15             path.removeLast();
16         }
17     }
18     public static List<List<Integer>> combinationSum(int[] nums,int target) {
19         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");
20         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
21     }
22     public static List<List<Integer>> baseline(int[] nums,int target) {
23         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");Set<List<Integer>> unique=new TreeSet<>(Solution::compare);
24         for(int mask=0;mask<(1<<a.length);mask++){long sum=0;List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0){sum+=a[i];row.add(a[i]);}if(sum==target)unique.add(row);}return new ArrayList<>(unique);
25     }
26 }
27

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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[false,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":1,"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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":2,"choice":1}]
rows
[]
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":2,"choice":1},{"start":2,"remaining":1,"next":2,"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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":2,"choice":1},{"start":2,"remaining":1,"next":3,"choice":null}]
rows
[]
phase
"prune"
candidate
2
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":2,"choice":1}]
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":2,"choice":null}]
rows
[]
phase
"undo"
candidate
1
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":3,"choice":2}]
rows
[]
phase
"choose"
candidate
2
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":3,"choice":2},{"start":3,"remaining":0,"next":3,"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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":3,"choice":2},{"start":3,"remaining":0,"next":3,"choice":null}]
rows
[[1,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":3,"choice":2}]
rows
[[1,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0},{"start":1,"remaining":2,"next":3,"choice":null}]
rows
[[1,2]]
phase
"undo"
candidate
2
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":0}]
rows
[[1,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":1,"choice":null}]
rows
[[1,2]]
phase
"undo"
candidate
0
Skip a symmetric sibling choice, not all equal values.
An earlier equal occurrence owns this sibling branch. A deeper frame may still choose another equal value when multiplicity allows it.
input
{"nums":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":2,"choice":null}]
rows
[[1,2]]
phase
"skip-duplicate"
candidate
1
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":3,"choice":2}]
rows
[[1,2]]
phase
"choose"
candidate
2
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":3,"choice":2},{"start":3,"remaining":1,"next":3,"choice":null}]
rows
[[1,2]]
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":3,"choice":2}]
rows
[[1,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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":3,"next":3,"choice":null}]
rows
[[1,2]]
phase
"undo"
candidate
2
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[]
rows
[[1,2]]
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":[1,1,2],"target":3}
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[]
rows
[[1,2]]
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
[[1,2]]

A single occurrence cannot be reused

Input: {"nums":[2],"target":4} · Single-use target combinations: []

Step 1 of 9: 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.

Single-use combinations — occurrence supply and duplicate pruning

Phase: initial.

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

Target: 4. Each occurrence is consumed once; the child frontier advances past its index.

Sorted occurrence positions — equal values still have separate supply

index 0: 2not 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],"target":4}`
sorted	`[2]`
path	`[]`
chosenIndices	`[]`
used	`[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>20)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");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(i>start&&a[i]==a[i-1])continue;
12             if(a[i]>remaining)break;
13             path.add(a[i]);
14             search(a,i+1,remaining-a[i],path,result);
15             path.removeLast();
16         }
17     }
18     public static List<List<Integer>> combinationSum(int[] nums,int target) {
19         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");
20         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
21     }
22     public static List<List<Integer>> baseline(int[] nums,int target) {
23         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");Set<List<Integer>> unique=new TreeSet<>(Solution::compare);
24         for(int mask=0;mask<(1<<a.length);mask++){long sum=0;List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0){sum+=a[i];row.add(a[i]);}if(sum==target)unique.add(row);}return new ArrayList<>(unique);
25     }
26 }
27

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],"target":4}
sorted
[2]
path
[]
chosenIndices
[]
used
[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],"target":4}
sorted
[2]
path
[]
chosenIndices
[]
used
[false]
frames
[{"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":[2],"target":4}
sorted
[2]
path
[2]
chosenIndices
[0]
used
[false]
frames
[{"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":[2],"target":4}
sorted
[2]
path
[2]
chosenIndices
[0]
used
[false]
frames
[{"start":0,"remaining":4,"next":1,"choice":0},{"start":1,"remaining":2,"next":1,"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":[2],"target":4}
sorted
[2]
path
[2]
chosenIndices
[0]
used
[false]
frames
[{"start":0,"remaining":4,"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],"target":4}
sorted
[2]
path
[]
chosenIndices
[]
used
[false]
frames
[{"start":0,"remaining":4,"next":1,"choice":null}]
rows
[]
phase
"undo"
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],"target":4}
sorted
[2]
path
[]
chosenIndices
[]
used
[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],"target":4}
sorted
[2]
path
[]
chosenIndices
[]
used
[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 has an empty selection

Input: {"nums":[1,1],"target":0} · Single-use 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.

Single-use combinations — occurrence supply and duplicate pruning

Phase: initial.

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

Target: 0. Each occurrence is consumed once; the child frontier advances past its index.

Sorted occurrence positions — equal values still have separate supply

index 0: 1not chosen on path
index 1: 1not 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":[1,1],"target":0}`
sorted	`[1,1]`
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>20)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");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(i>start&&a[i]==a[i-1])continue;
12             if(a[i]>remaining)break;
13             path.add(a[i]);
14             search(a,i+1,remaining-a[i],path,result);
15             path.removeLast();
16         }
17     }
18     public static List<List<Integer>> combinationSum(int[] nums,int target) {
19         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");
20         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
21     }
22     public static List<List<Integer>> baseline(int[] nums,int target) {
23         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");Set<List<Integer>> unique=new TreeSet<>(Solution::compare);
24         for(int mask=0;mask<(1<<a.length);mask++){long sum=0;List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0){sum+=a[i];row.add(a[i]);}if(sum==target)unique.add(row);}return new ArrayList<>(unique);
25     }
26 }
27

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":[1,1],"target":0}
sorted
[1,1]
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":[1,1],"target":0}
sorted
[1,1]
path
[]
chosenIndices
[]
used
[false,false]
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":[1,1],"target":0}
sorted
[1,1]
path
[]
chosenIndices
[]
used
[false,false]
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":[1,1],"target":0}
sorted
[1,1]
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":[1,1],"target":0}
sorted
[1,1]
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
[[]]

Long-safe extreme candidates

Input: {"nums":[2147483647,2147483647,1],"target":2147483647} · Single-use target combinations: [[2147483647]]

Step 1 of 16: 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.

Single-use combinations — occurrence supply and duplicate pruning

Phase: initial.

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

Target: 2147483647. Each occurrence is consumed once; the child frontier advances past its index.

Sorted occurrence positions — equal values still have separate supply

index 0: 1not chosen on path
index 1: 2147483647not chosen on path
index 2: 2147483647not 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":[2147483647,2147483647,1],"target":2147483647}`
sorted	`[1,2147483647,2147483647]`
path	`[]`
chosenIndices	`[]`
used	`[false,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>20)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");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(i>start&&a[i]==a[i-1])continue;
12             if(a[i]>remaining)break;
13             path.add(a[i]);
14             search(a,i+1,remaining-a[i],path,result);
15             path.removeLast();
16         }
17     }
18     public static List<List<Integer>> combinationSum(int[] nums,int target) {
19         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");
20         List<List<Integer>> result=new ArrayList<>();search(a,0,target,new ArrayList<>(),result);return result;
21     }
22     public static List<List<Integer>> baseline(int[] nums,int target) {
23         int[] a=sorted(nums);if(target<0)throw new IllegalArgumentException("invalid target");Set<List<Integer>> unique=new TreeSet<>(Solution::compare);
24         for(int mask=0;mask<(1<<a.length);mask++){long sum=0;List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0){sum+=a[i];row.add(a[i]);}if(sum==target)unique.add(row);}return new ArrayList<>(unique);
25     }
26 }
27

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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":1,"choice":0},{"start":1,"remaining":2147483646,"next":1,"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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":1,"choice":0},{"start":1,"remaining":2147483646,"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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[1]
chosenIndices
[0]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":1,"choice":null}]
rows
[]
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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[2147483647]
chosenIndices
[1]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":2,"choice":1}]
rows
[]
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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[2147483647]
chosenIndices
[1]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":2,"choice":1},{"start":2,"remaining":0,"next":2,"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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[2147483647]
chosenIndices
[1]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":2,"choice":1},{"start":2,"remaining":0,"next":2,"choice":null}]
rows
[[2147483647]]
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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[2147483647]
chosenIndices
[1]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":2,"choice":1}]
rows
[[2147483647]]
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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":2,"choice":null}]
rows
[[2147483647]]
phase
"undo"
candidate
1
Skip a symmetric sibling choice, not all equal values.
An earlier equal occurrence owns this sibling branch. A deeper frame may still choose another equal value when multiplicity allows it.
input
{"nums":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":2147483647,"next":3,"choice":null}]
rows
[[2147483647]]
phase
"skip-duplicate"
candidate
2
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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[]
rows
[[2147483647]]
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":[2147483647,2147483647,1],"target":2147483647}
sorted
[1,2147483647,2147483647]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[]
rows
[[2147483647]]
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
[[2147483647]]

Test the contract

Input: Two equal occurrences needed together
Output: the multiplicity-bearing row appears once
Checks local, rather than global, duplicate handling.
Input: Single occurrence with a double-value target
Output: []
Detects accidental reuse.
Input: All positive ternary arrays through length seven and targets 0..8
Output: canonical mask coverage
Independent checking uses occurrence masks and long sums.
Input: Repeated MAX values with target MAX
Output: one singleton row
Tests numeric boundaries and deduplication.
Input: Twenty equal ones, target ten
Output: one ten-entry row
Exercises supply limits and duplicate-heavy pruning.

Common mistakes and counterexamples

Reuse index i in the child

Counterexample: [2], target 4 would falsely produce [2,2].

Advance to i+1.

Delete duplicates before searching

Counterexample: [1,1,6], target 8 would lose its only solution.

Retain occurrences and prune only equal siblings.

Use i>0 for duplicate suppression

Counterexample: The second 1 would be forbidden even after choosing the first.

Compare i with this frame’s start.

Accumulate subset sums in int

Counterexample: MAX+MAX can wrap and corrupt baseline feasibility.

Use long in exhaustive oracles and guarded remaining subtraction in the main method.

Follow-ups

Allow reuse of values.

Switch the child frontier to i only after defining duplicate denominations and proving a strictly decreasing positive remaining sum. DSA-122 rejects duplicate reusable denominations rather than treating their occurrences as different types.

Permit negative occurrences with single use.

Index progress still guarantees termination, but positive overshoot pruning is invalid. Remove that break or derive lower/upper achievable suffix bounds; use long or exact arithmetic to define sums safely.

Count unique combinations using grouped multiplicities.

Compress equal values and iterate allowed counts for each value group. A DP state must distinguish value groups from occurrence indices so equal-occurrence assignments are not counted multiple times.

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 · 219/20,000 characters

Self-review

Can I explain why i+1 and i>start are both necessary?Can I keep duplicate supply without emitting duplicate answers?Can I justify positivity-based pruning and full-int arithmetic safety?

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

Related foundations

Keep practicing

Open focused practice

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