DSA-119 · FOCUSED PRACTICE
Subsets II — Duplicates
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 6571 deterministic checks. Learner drafts are not executed.
Understand the problem
Return every distinct value subset of nums, including the empty subset. Each occurrence can be selected at most once, so repeated input values can appear together up to their available multiplicity.
- nums is nonnull, contains at most 16 signed int values, and may contain duplicates. Null throws NullPointerException; length above 16 throws IllegalArgumentException. The materialization bound is enforced because a distinct 16-value input already has 65,536 subsets.
- subsetsWithDup returns rows in lexicographic value order, with each row nondecreasing and a shorter prefix ordered before its extensions. Empty input returns [[]]. Distinct equal-value occurrences do not create duplicate output rows; this API returns values rather than occurrence IDs.
- 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.
Examples
Input:
[2,1,2]
Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]Sorting a clone makes equal choices adjacent; two copies of 2 may be chosen on successive depths.
Input:
[]
Output:[[]]The root path is a valid subset and must be emitted.
Input:
[7,7,7]
Output:[[],[7],[7,7],[7,7,7]]Four multiplicity choices exist, rather than eight distinct value subsets.
Before you start
- Increasing-index subset enumeration from DSA-118
- Why duplicate occurrences and duplicate value results are different
Recognize the structure
DSA-118 has one path per increasing index sequence. Equal values break the implication that different index sequences mean different value answers. Preserve increasing indices to prevent reusing an occurrence, but additionally assign equal sibling branches to their first eligible occurrence. Sorting is a symmetry reduction, not a license to change the caller’s array.
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.
No unsaved text changes · 203/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Keep the increasing-index frontier from ordinary subsets.
Hint 2
Sort a clone so equal sibling choices become adjacent.
Hint 3
Emit a snapshot at entry, skip i>start duplicates, recurse from i+1, then undo.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate every occurrence mask, then deduplicate
Sort a clone and visit every bit mask. Build its selected value row in index order, then insert that independent row into a TreeSet with a numeric lexicographic comparator. Equal value rows from different masks collapse. This compiling baseline is complete and easy to verify, but still generates all 2^n occurrence subsets and pays for ordered-set comparisons after doing duplicate work.
Improve the baseline
Give a frame a start frontier
The path is already a valid subset, so copy it at every recursive entry. The frame may choose any i≥start; its child starts at i+1, guaranteeing that no occurrence is selected twice. The root therefore accounts for the empty subset.
Skip only equal siblings
After sorting, if i>start and a[i]==a[i−1], the earlier sibling already explores every continuation beginning with that value. Skip this candidate in the current frame. Do not test only i>0: a child with start=i is allowed to select another equal occurrence and represent multiplicity.
Restore the path after every child
Append a[i], explore the child completely, then remove exactly the last value. Copy on emission so later removal cannot edit stored answers. Preorder emission plus ascending candidate values produces the documented numeric lexicographic order, including prefix-before-extension behavior.
Why it is correct
Sound multiplicities
Chosen indices are strictly increasing. Each selected occurrence is real and unique, so no row uses any value more often than nums supplies it. Sorting ensures the row’s values are nondecreasing.
Completeness by canonical occurrence choices
For any desired value multiset within the supplied counts, choose the earliest eligible occurrences of each needed value in order. The first such occurrence at each frame is never skipped, and the loop reaches it. Thus every permissible multiplicity vector has a surviving search path.
Uniqueness and order
Suppose two surviving paths produced the same row and consider their first differing occurrence choice. The values there must be equal. The later equal sibling would have been skipped, a contradiction. Ascending first differences and emission before extension give lexicographic output. Depth strictly increases the start frontier and is at most n, so the traversal terminates.
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);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,List<Integer> path,List<List<Integer>> result) {
result.add(new ArrayList<>(path));
for(int i=start;i<a.length;i++) {
if(i>start&&a[i]==a[i-1])continue;
path.add(a[i]);
search(a,i+1,path,result);
path.removeLast();
}
}
public static List<List<Integer>> subsetsWithDup(int[] nums) {
int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,0,new ArrayList<>(),result);return result;
}
public static List<List<Integer>> baseline(int[] nums) {
int[] a=sorted(nums);Set<List<Integer>> unique=new TreeSet<>(Solution::compare);
for(int mask=0;mask<(1<<a.length);mask++){List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0)row.add(a[i]);unique.add(row);}return new ArrayList<>(unique);
}
}
Read the meaningful blocks
Duplicate pruning belongs to the frame
The condition i>start describes siblings of this exact recursive call. On [2,2], the root skips starting with occurrence one after occurrence zero’s branch, but occurrence zero’s child may still choose occurrence one and emit [2,2].
Snapshots own their contents
new ArrayList<>(path) is necessary even when the algorithm immediately recurses. All stored rows would otherwise be aliases of one mutable path and would shrink during undo. The outer result and every row are mutable but independent on repeated calls as well.
Compare signed ints without subtraction in Java
Arrays.sort orders a cloned int array safely across MIN/MAX. The baseline comparator uses Integer.compare at the first differing position, then compares row lengths; subtracting values could overflow and violate TreeSet ordering.
Complexity
Let n be input length, U=∏(count(value)+1) the number of unique subsets, and S the total number of returned integer entries. Main time is O(n log(n+1)+nU+1), including candidate scans and snapshot copying; S≤nU. Output storage is Θ(U+S), and auxiliary sorted copy, path and recursion use O(n+1). For distinct n≥1, U=2^n and S=n2^(n−1), so materialization costs Θ(n2^n).
The mask baseline builds 2^n candidate rows and orders unique answers. A safe bound is O(n log(n+1)+n2^n(1+log(U+1))+1) time because a TreeSet comparison can inspect n values. Live storage is O(U+S+n+1), including retained output rows and set nodes. For all-equal values, only n+1 answers remain, but mask generation is still exponential.
Exact-state walkthroughs
Reveal normal and boundary traces
Equal siblings collapse while deeper copies remain
Input: [2,1,2] · Unique value subsets: [[],[1],[1,2],[1,2,2],[2],[2,2]]
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.
Phase: initial.
Original input: [2,1,2]. Only the private sorted copy is used for ordered choices.
Sorted occurrence positions — equal values still have separate supply
- index 0: 1not chosen on path
- index 1: 2not 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.
Every entered subset path is emitted, including empty. 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.
| Variable | Value |
|---|---|
| input | [2,1,2] |
| sorted | [1,2,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>16)throw new IllegalArgumentException("materialization limit"); 5 int[] a=nums.clone();Arrays.sort(a);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,List<Integer> path,List<List<Integer>> result) { 9 result.add(new ArrayList<>(path)); 10 for(int i=start;i<a.length;i++) { 11 if(i>start&&a[i]==a[i-1])continue; 12 path.add(a[i]); 13 search(a,i+1,path,result); 14 path.removeLast(); 15 } 16 } 17 public static List<List<Integer>> subsetsWithDup(int[] nums) { 18 int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,0,new ArrayList<>(),result);return result; 19 } 20 public static List<List<Integer>> baseline(int[] nums) { 21 int[] a=sorted(nums);Set<List<Integer>> unique=new TreeSet<>(Solution::compare); 22 for(int mask=0;mask<(1<<a.length);mask++){List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0)row.add(a[i]);unique.add(row);}return new ArrayList<>(unique); 23 } 24 } 25
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
[2,1,2]- sorted
[1,2,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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":0,"choice":null}]- rows
[[]]- phase
"emit"
- 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
[2,1,2]- sorted
[1,2,2]- path
[1]- chosenIndices
[0]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"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
[2,1,2]- sorted
[1,2,2]- path
[1]- chosenIndices
[0]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":1,"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
[2,1,2]- sorted
[1,2,2]- path
[1]- chosenIndices
[0]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":1,"choice":null}]- rows
[[],[1]]- phase
"emit"
- 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
[2,1,2]- sorted
[1,2,2]- path
[1,2]- chosenIndices
[0,1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1}]- rows
[[],[1]]- 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
[2,1,2]- sorted
[1,2,2]- path
[1,2]- chosenIndices
[0,1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[1]]- 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
[2,1,2]- sorted
[1,2,2]- path
[1,2]- chosenIndices
[0,1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[1],[1,2]]- phase
"emit"
- 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
[2,1,2]- sorted
[1,2,2]- path
[1,2,2]- chosenIndices
[0,1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2}]- rows
[[],[1],[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
[2,1,2]- sorted
[1,2,2]- path
[1,2,2]- chosenIndices
[0,1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2},{"start":3,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,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
[2,1,2]- sorted
[1,2,2]- path
[1,2,2]- chosenIndices
[0,1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2},{"start":3,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[1,2,2]- chosenIndices
[0,1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[1,2]- chosenIndices
[0,1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,2,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
[2,1,2]- sorted
[1,2,2]- path
[1,2]- chosenIndices
[0,1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[1]- chosenIndices
[0]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":null}]- rows
[[],[1],[1,2],[1,2,2]]- 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
[2,1,2]- sorted
[1,2,2]- path
[1]- chosenIndices
[0]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,2,2]]- 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
[2,1,2]- sorted
[1,2,2]- path
[1]- chosenIndices
[0]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":null}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[2]- chosenIndices
[1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[2]- chosenIndices
[1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[2]- chosenIndices
[1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[1],[1,2],[1,2,2],[2]]- phase
"emit"
- 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
[2,1,2]- sorted
[1,2,2]- path
[2,2]- chosenIndices
[1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2}]- rows
[[],[1],[1,2],[1,2,2],[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
[2,1,2]- sorted
[1,2,2]- path
[2,2]- chosenIndices
[1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2},{"start":3,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,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
[2,1,2]- sorted
[1,2,2]- path
[2,2]- chosenIndices
[1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2},{"start":3,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,2,2],[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
[2,1,2]- sorted
[1,2,2]- path
[2,2]- chosenIndices
[1,2]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":2}]- rows
[[],[1],[1,2],[1,2,2],[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
[2,1,2]- sorted
[1,2,2]- path
[2]- chosenIndices
[1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,2,2],[2],[2,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
[2,1,2]- sorted
[1,2,2]- path
[2]- chosenIndices
[1]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1}]- rows
[[],[1],[1,2],[1,2,2],[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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":null}]- rows
[[],[1],[1,2],[1,2,2],[2],[2,2]]- 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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[{"start":0,"remaining":null,"next":3,"choice":null}]- rows
[[],[1],[1,2],[1,2,2],[2],[2,2]]- 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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[]- rows
[[],[1],[1,2],[1,2,2],[2],[2,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
[2,1,2]- sorted
[1,2,2]- path
[]- chosenIndices
[]- used
[false,false,false]- frames
[]- rows
[[],[1],[1,2],[1,2,2],[2],[2,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],[1,2],[1,2,2],[2],[2,2]]
All-equal multiplicities
Input: [2,2] · Unique value subsets: [[],[2],[2,2]]
Step 1 of 17: 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.
Phase: initial.
Original input: [2,2]. Only the private sorted copy is used for ordered choices.
Sorted occurrence positions — equal values still have separate supply
- index 0: 2not chosen on path
- index 1: 2not chosen on path
Working path — snapshots are copied only at valid emission points
Empty.
Independent rows emitted so far: 0
Empty.
Every entered subset path is emitted, including empty. 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.
| Variable | Value |
|---|---|
| input | [2,2] |
| sorted | [2,2] |
| 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);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,List<Integer> path,List<List<Integer>> result) { 9 result.add(new ArrayList<>(path)); 10 for(int i=start;i<a.length;i++) { 11 if(i>start&&a[i]==a[i-1])continue; 12 path.add(a[i]); 13 search(a,i+1,path,result); 14 path.removeLast(); 15 } 16 } 17 public static List<List<Integer>> subsetsWithDup(int[] nums) { 18 int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,0,new ArrayList<>(),result);return result; 19 } 20 public static List<List<Integer>> baseline(int[] nums) { 21 int[] a=sorted(nums);Set<List<Integer>> unique=new TreeSet<>(Solution::compare); 22 for(int mask=0;mask<(1<<a.length);mask++){List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0)row.add(a[i]);unique.add(row);}return new ArrayList<>(unique); 23 } 24 } 25
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
[2,2]- sorted
[2,2]- 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
[2,2]- sorted
[2,2]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"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
[2,2]- sorted
[2,2]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":0,"choice":null}]- rows
[[]]- phase
"emit"
- 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
[2,2]- sorted
[2,2]- path
[2]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"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
[2,2]- sorted
[2,2]- path
[2]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":1,"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
[2,2]- sorted
[2,2]- path
[2]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":1,"choice":null}]- rows
[[],[2]]- phase
"emit"
- 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
[2,2]- sorted
[2,2]- path
[2,2]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1}]- rows
[[],[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
[2,2]- sorted
[2,2]- path
[2,2]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[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
[2,2]- sorted
[2,2]- path
[2,2]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"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
[2,2]- sorted
[2,2]- path
[2,2]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"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
[2,2]- sorted
[2,2]- path
[2]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"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
[2,2]- sorted
[2,2]- path
[2]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"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
[2,2]- sorted
[2,2]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":null}]- rows
[[],[2],[2,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
[2,2]- sorted
[2,2]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":null}]- rows
[[],[2],[2,2]]- phase
"skip-duplicate"- 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
[2,2]- sorted
[2,2]- path
[]- chosenIndices
[]- used
[false,false]- frames
[]- rows
[[],[2],[2,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
[2,2]- sorted
[2,2]- path
[]- chosenIndices
[]- used
[false,false]- frames
[]- rows
[[],[2],[2,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
[[],[2],[2,2]]
The empty subset
Input: [] · Unique value subsets: [[]]
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.
Phase: initial.
Original input: []. Only the private sorted copy is used for ordered choices.
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.
Every entered subset path is emitted, including empty. 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.
| Variable | Value |
|---|---|
| input | [] |
| 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);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,List<Integer> path,List<List<Integer>> result) { 9 result.add(new ArrayList<>(path)); 10 for(int i=start;i<a.length;i++) { 11 if(i>start&&a[i]==a[i-1])continue; 12 path.add(a[i]); 13 search(a,i+1,path,result); 14 path.removeLast(); 15 } 16 } 17 public static List<List<Integer>> subsetsWithDup(int[] nums) { 18 int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,0,new ArrayList<>(),result);return result; 19 } 20 public static List<List<Integer>> baseline(int[] nums) { 21 int[] a=sorted(nums);Set<List<Integer>> unique=new TreeSet<>(Solution::compare); 22 for(int mask=0;mask<(1<<a.length);mask++){List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0)row.add(a[i]);unique.add(row);}return new ArrayList<>(unique); 23 } 24 } 25
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
[]- 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
[]- sorted
[]- path
[]- chosenIndices
[]- used
[]- frames
[{"start":0,"remaining":null,"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
[]- sorted
[]- path
[]- chosenIndices
[]- used
[]- frames
[{"start":0,"remaining":null,"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
[]- 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
[]- 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
[[]]
Signed extreme values sort safely
Input: [2147483647,-2147483648] · Unique value subsets: [[],[-2147483648],[-2147483648,2147483647],[2147483647]]
Step 1 of 21: 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.
Phase: initial.
Original input: [2147483647,-2147483648]. Only the private sorted copy is used for ordered choices.
Sorted occurrence positions — equal values still have separate supply
- index 0: -2147483648not chosen on path
- index 1: 2147483647not chosen on path
Working path — snapshots are copied only at valid emission points
Empty.
Independent rows emitted so far: 0
Empty.
Every entered subset path is emitted, including empty. 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.
| Variable | Value |
|---|---|
| input | [2147483647,-2147483648] |
| sorted | [-2147483648,2147483647] |
| 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);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,List<Integer> path,List<List<Integer>> result) { 9 result.add(new ArrayList<>(path)); 10 for(int i=start;i<a.length;i++) { 11 if(i>start&&a[i]==a[i-1])continue; 12 path.add(a[i]); 13 search(a,i+1,path,result); 14 path.removeLast(); 15 } 16 } 17 public static List<List<Integer>> subsetsWithDup(int[] nums) { 18 int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,0,new ArrayList<>(),result);return result; 19 } 20 public static List<List<Integer>> baseline(int[] nums) { 21 int[] a=sorted(nums);Set<List<Integer>> unique=new TreeSet<>(Solution::compare); 22 for(int mask=0;mask<(1<<a.length);mask++){List<Integer> row=new ArrayList<>();for(int i=0;i<a.length;i++)if((mask&(1<<i))!=0)row.add(a[i]);unique.add(row);}return new ArrayList<>(unique); 23 } 24 } 25
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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":0,"choice":null}]- rows
[[]]- phase
"emit"
- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":1,"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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":1,"choice":null}]- rows
[[],[-2147483648]]- phase
"emit"
- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648,2147483647]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1}]- rows
[[],[-2147483648]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648,2147483647]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[-2147483648]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648,2147483647]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[-2147483648],[-2147483648,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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648,2147483647]- chosenIndices
[0,1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":1}]- rows
[[],[-2147483648],[-2147483648,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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":1,"remaining":null,"next":2,"choice":null}]- rows
[[],[-2147483648],[-2147483648,2147483647]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[-2147483648]- chosenIndices
[0]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":0}]- rows
[[],[-2147483648],[-2147483648,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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":1,"choice":null}]- rows
[[],[-2147483648],[-2147483648,2147483647]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[2147483647]- chosenIndices
[1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1}]- rows
[[],[-2147483648],[-2147483648,2147483647]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[2147483647]- chosenIndices
[1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[-2147483648],[-2147483648,2147483647]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[2147483647]- chosenIndices
[1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":2,"remaining":null,"next":2,"choice":null}]- rows
[[],[-2147483648],[-2147483648,2147483647],[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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[2147483647]- chosenIndices
[1]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":1}]- rows
[[],[-2147483648],[-2147483648,2147483647],[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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[]- chosenIndices
[]- used
[false,false]- frames
[{"start":0,"remaining":null,"next":2,"choice":null}]- rows
[[],[-2147483648],[-2147483648,2147483647],[2147483647]]- 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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[]- chosenIndices
[]- used
[false,false]- frames
[]- rows
[[],[-2147483648],[-2147483648,2147483647],[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
[2147483647,-2147483648]- sorted
[-2147483648,2147483647]- path
[]- chosenIndices
[]- used
[false,false]- frames
[]- rows
[[],[-2147483648],[-2147483648,2147483647],[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
[[],[-2147483648],[-2147483648,2147483647],[2147483647]]
Test the contract
Input:
Empty input
Output:[[]]One empty subset exists.
Input:
All equal values
Output:n+1 multiplicity rowsProhibits both over-pruning and duplicate emission.
Input:
MIN/MAX and unsorted duplicates
Output:correct numeric lexicographic rowsComparator overflow and source mutation are tested.
Input:
Every ternary array through length seven
Output:matches occurrence-mask canonical coverageIndependent output checking includes all lengths and multiplicities.
Input:
Sixteen distinct values
Output:65,536 independent rowsExercises the enforced materialization boundary.
Common mistakes and counterexamples
Skip every value equal to its predecessor
Counterexample: [2,2] must include [2,2].
Skip only when i>start, so deeper frames can use remaining multiplicity.
Use a global value-visited set
Counterexample: Choosing a 2 once would wrongly prevent a second available 2 at a deeper depth.
Track the index frontier and canonical sibling ownership.
Sort nums directly
Counterexample: The caller supplied [2,1,2] and expects its order preserved.
Clone before sorting, including on later validation failures.
Store path directly
Counterexample: All previously emitted rows change during removeLast.
Allocate a fresh row for every emission.
Follow-ups
Represent answers as value-frequency vectors.
Compress equal runs into (value,count) pairs and choose a quantity from zero through each count. This makes the multiplicity-vector proof explicit and can reduce repeated sibling scanning; expand values only when an actual row is emitted.
Return only subsets of size k.
Add a remaining-size resource. Prune when the path is too long or too few occurrences remain, while retaining sibling duplicate suppression. Count output copying separately rather than claiming polynomial total enumeration.
Stream subsets lazily.
Keep explicit frames across iterator calls and return independent snapshots. This reduces retained output memory but must preserve duplicate ownership, order, cancellation behavior and source immutability.