DSA-121 · Canonical occurrence order removes symmetric permutation branches

Permutations II — Duplicates

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return every distinct value permutation of nums, which may contain repeated integers. Every row must use the full input multiset exactly once, without duplicate value rows.

nums is nonnull with at most nine signed int values; duplicates are valid. Null throws NullPointerException and length above nine throws IllegalArgumentException. All input values, including MIN/MAX, are supported.
permute returns unique rows in numeric lexicographic order. Empty input returns [[]]. Different equal-value occurrence assignments are the same value result, while different value orders remain distinct. No multiplicity may be lost.
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: [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
The six labeled occurrence arrangements collapse into three value arrangements.
Input: [4,4,4]
Output: [[4,4,4]]
All three copies must appear in the only output row.
Input: []
Output: [[]]
One empty permutation exists.

Before you start

Used-index permutation traversal from DSA-120
Sibling symmetry and canonical representatives for duplicates

Recognize the structure

A used array prevents selecting the same occurrence twice, but equal occurrences still generate interchangeable branches. Sort the private copy and require equal occurrences to be consumed in their index order along a path. This picks one representative occurrence sequence for each value permutation without changing the set of returned value sequences.

Try before revealing

Hint 1

Keep a used bit for each occurrence, including equal copies.

Hint 2

Equivalent equal copies should be consumed in one canonical index order.

Hint 3

Skip a later equal occurrence while the preceding equal one is unused; emit only full paths.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Generate labeled insertion permutations, then deduplicate

Insert each occurrence into every position of every partial row, as in DSA-120. Equal values still create all n! labeled arrangements. A lexicographic TreeSet removes repeated value rows only after full generation. The baseline is complete but wasteful for duplicate-heavy inputs; nine equal occurrences yield one answer after 362,880 labeled candidate rows.

Improve the baseline

Keep path-local occurrence ownership

used[i] remains necessary: even identical values have separate available counts. A valid output contains all n occurrences, so emitting only distinct values or using a global set would incorrectly erase multiplicity.

Require the previous equal occurrence first

After skipping an already used i, skip i when i>0, a[i]==a[i−1], and used[i−1] is false. At this frame the earlier equal occurrence owns the symmetric sibling. If that earlier copy is already on the path, the current copy is available for the next position.

Copy at a complete leaf and undo normally

The remaining traversal is the same choose/mark/recurse/unmark structure as distinct permutations. Ascending sorted choices give numeric lexicographic order. Duplicate pruning changes which branches exist, not the need for fresh result rows and exact restoration.

Why it is correct

Sound complete rows

Each chosen index is unused and is then marked, so no occurrence can be repeated. At path length n, all occurrences are represented and the row has exactly the source multiplicities.

Canonical representative exists

For any desired value permutation, assign occurrences of each equal value from left to right in sorted-index order as they appear in that row. Every assigned occurrence is unused, and its previous equal occurrence has already been used if one exists. Thus the canonical path is never pruned.

Only one representative survives

For a repeated value, a later occurrence cannot be chosen before its unused predecessor. Therefore equal occurrences must be consumed in their fixed index order on every surviving path. One value row has exactly one such assignment, so no duplicate leaf can survive. Depth n guarantees termination and ascending value choices determine output order.

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>9)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,boolean[] used,List<Integer> path,List<List<Integer>> result) {
        if(path.size()==a.length){result.add(new ArrayList<>(path));return;}
        for(int i=0;i<a.length;i++) {
            if(used[i])continue;
            if(i>0&&a[i]==a[i-1]&&!used[i-1])continue;
            used[i]=true;path.add(a[i]);
            search(a,used,path,result);
            path.removeLast();used[i]=false;
        }
    }
    public static List<List<Integer>> permute(int[] nums) {
        int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
    }
    public static List<List<Integer>> baseline(int[] nums) {
        int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
        for(int value:a){List<List<Integer>> next=new ArrayList<>();for(List<Integer> row:rows)for(int at=0;at<=row.size();at++){List<Integer> copy=new ArrayList<>(row);copy.add(at,value);next.add(copy);}rows=next;}
        Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
    }
}

Read the meaningful blocks

The unused predecessor test is deliberate

The rule is !used[i−1], not used[i−1]. For [1,1,2], after choosing the first 1 the second must be legal at the next depth. Reversing the condition rejects the canonical order described by this implementation and its proof.

An equal value is not globally forbidden

After one 1 is used, another copy represents a different occurrence that is required to complete the multiset. The skip only removes a symmetric next-choice branch while that preceding equal occurrence is still available.

Duplicate pruning does not make output polynomial

If all values differ, there are still n! rows. If all values are equal, the main algorithm follows one path but scans all n indices at each level, so this particular used-array loop still does quadratic scanning. A frequency-based follow-up can reduce that overhead.

Complexity

Let P=n!/∏count(value)! be unique permutations and H the number of distinct surviving prefixes, including root and leaves. Main time is O(n log(n+1)+nH+nP+1), with Θ(P+nP) returned list/entry storage and O(n+1) auxiliary space. Since H≤(n+1)P, O(n²P+n log(n+1)+1) is a safe output-count bound. For distinct values, the familiar Θ(n·n!) bound applies; for all equal values, P=1 and scanning is O(n²).

The insertion baseline still builds n! labeled rows before deduplication. A safe time bound is O(n log(n+1)+(n+1)(n!+1)(1+log(P+1))) because row comparison/copying costs up to n. Retaining labeled generations can use O((n+1)(n!+1)) space even when the final output has one row. No claim that post-generation deduplication saves that work or memory is made.

Exact-state walkthroughs

Reveal normal and boundary traces

A used earlier equal copy permits the next equal copy

Input: [1,1,2] · Unique multiset permutations: [[1,1,2],[1,2,1],[2,1,1]]

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

Unique permutations — canonical equal-occurrence order

Phase: initial.

Original input: [1,1,2]. Only the private sorted copy is used for ordered choices.

Sorted occurrence positions — equal values still have separate supply

index 0: 1available
index 1: 1available
index 2: 2available

Working path — snapshots are copied only at valid emission points

Empty.

Independent rows emitted so far: 0

Empty.

Only full-length arrangements 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	`[1,1,2]`
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>9)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,boolean[] used,List<Integer> path,List<List<Integer>> result) {
 9         if(path.size()==a.length){result.add(new ArrayList<>(path));return;}
10         for(int i=0;i<a.length;i++) {
11             if(used[i])continue;
12             if(i>0&&a[i]==a[i-1]&&!used[i-1])continue;
13             used[i]=true;path.add(a[i]);
14             search(a,used,path,result);
15             path.removeLast();used[i]=false;
16         }
17     }
18     public static List<List<Integer>> permute(int[] nums) {
19         int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
20     }
21     public static List<List<Integer>> baseline(int[] nums) {
22         int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
23         for(int value:a){List<List<Integer>> next=new ArrayList<>();for(List<Integer> row:rows)for(int at=0;at<=row.size();at++){List<Integer> copy=new ArrayList<>(row);copy.add(at,value);next.add(copy);}rows=next;}
24         Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
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
[1,1,2]
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
[1,1,2]
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":null,"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
[1,1,2]
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[true,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
[1,1,2]
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[true,false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[]
phase
"enter"
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[true,false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[true,true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"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
[1,1,2]
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[true,true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[]
phase
"enter"
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[true,true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[]
phase
"skip-used"
candidate
0
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[true,true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[1,1,2]
chosenIndices
[0,1,2]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"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
[1,1,2]
sorted
[1,1,2]
path
[1,1,2]
chosenIndices
[0,1,2]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":3,"choice":2},{"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
[1,1,2]
sorted
[1,1,2]
path
[1,1,2]
chosenIndices
[0,1,2]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,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
[1,1,2]
sorted
[1,1,2]
path
[1,1,2]
chosenIndices
[0,1,2]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":3,"choice":2}]
rows
[[1,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
[1,1,2]
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[true,true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":3,"choice":null}]
rows
[[1,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
[1,1,2]
sorted
[1,1,2]
path
[1,1]
chosenIndices
[0,1]
used
[true,true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[1,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
[1,1,2]
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[true,false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,1,2]]
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
[1,1,2]
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"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
[1,1,2]
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,1,2]]
phase
"enter"
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[1,1,2]]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[1,2,1]
chosenIndices
[0,2,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[1,1,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
[1,1,2]
sorted
[1,1,2]
path
[1,2,1]
chosenIndices
[0,2,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"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
[1,1,2]
sorted
[1,1,2]
path
[1,2,1]
chosenIndices
[0,2,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[1,2,1]
chosenIndices
[0,2,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,1,2],[1,2,1]]
phase
"undo"
candidate
1
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":3,"choice":null}]
rows
[[1,1,2],[1,2,1]]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[1,2]
chosenIndices
[0,2]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":2}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[true,false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":null}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[1]
chosenIndices
[0]
used
[true,false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2,1]
chosenIndices
[2,0]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[1,1,2],[1,2,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2,1]
chosenIndices
[2,0]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,1,2],[1,2,1]]
phase
"enter"
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[2,1]
chosenIndices
[2,0]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[1,1,2],[1,2,1]]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[2,1,1]
chosenIndices
[2,0,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[1,1,2],[1,2,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
[1,1,2]
sorted
[1,1,2]
path
[2,1,1]
chosenIndices
[2,0,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,1,2],[1,2,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
[1,1,2]
sorted
[1,1,2]
path
[2,1,1]
chosenIndices
[2,0,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2,1,1]
chosenIndices
[2,0,1]
used
[true,true,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2,1]
chosenIndices
[2,0]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
phase
"undo"
candidate
1
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[2,1]
chosenIndices
[2,0]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":3,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[2,1]
chosenIndices
[2,0]
used
[true,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
phase
"skip-duplicate"
candidate
1
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[1,1,2]
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2},{"start":0,"remaining":null,"next":3,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
phase
"skip-used"
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
[1,1,2]
sorted
[1,1,2]
path
[2]
chosenIndices
[2]
used
[false,false,true]
frames
[{"start":0,"remaining":null,"next":3,"choice":2}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[{"start":0,"remaining":null,"next":3,"choice":null}]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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
[1,1,2]
sorted
[1,1,2]
path
[]
chosenIndices
[]
used
[false,false,false]
frames
[]
rows
[[1,1,2],[1,2,1],[2,1,1]]
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,1],[2,1,1]]

All equal copies remain required

Input: [2,2] · Unique multiset permutations: [[2,2]]

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.

Unique permutations — canonical equal-occurrence order

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: 2available
index 1: 2available

Working path — snapshots are copied only at valid emission points

Empty.

Independent rows emitted so far: 0

Empty.

Only full-length arrangements 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	`[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>9)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,boolean[] used,List<Integer> path,List<List<Integer>> result) {
 9         if(path.size()==a.length){result.add(new ArrayList<>(path));return;}
10         for(int i=0;i<a.length;i++) {
11             if(used[i])continue;
12             if(i>0&&a[i]==a[i-1]&&!used[i-1])continue;
13             used[i]=true;path.add(a[i]);
14             search(a,used,path,result);
15             path.removeLast();used[i]=false;
16         }
17     }
18     public static List<List<Integer>> permute(int[] nums) {
19         int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
20     }
21     public static List<List<Integer>> baseline(int[] nums) {
22         int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
23         for(int value:a){List<List<Integer>> next=new ArrayList<>();for(List<Integer> row:rows)for(int at=0;at<=row.size();at++){List<Integer> copy=new ArrayList<>(row);copy.add(at,value);next.add(copy);}rows=next;}
24         Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
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
[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"
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
[true,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
[true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[]
phase
"enter"
This occurrence is already in the current permutation.
Occurrence ownership is path-local. A sibling branch may use the same position after its previous owner is undone.
input
[2,2]
sorted
[2,2]
path
[2]
chosenIndices
[0]
used
[true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[]
phase
"skip-used"
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,2]
sorted
[2,2]
path
[2,2]
chosenIndices
[0,1]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"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
[2,2]
sorted
[2,2]
path
[2,2]
chosenIndices
[0,1]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"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
[2,2]
chosenIndices
[0,1]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[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
[true,true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[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
[true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[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
[true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[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]]
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]]
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]]
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]]
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]]

Empty multiset

Input: [] · Unique multiset permutations: [[]]

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.

Unique permutations — canonical equal-occurrence order

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.

Only full-length arrangements 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	`[]`
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>9)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,boolean[] used,List<Integer> path,List<List<Integer>> result) {
 9         if(path.size()==a.length){result.add(new ArrayList<>(path));return;}
10         for(int i=0;i<a.length;i++) {
11             if(used[i])continue;
12             if(i>0&&a[i]==a[i-1]&&!used[i-1])continue;
13             used[i]=true;path.add(a[i]);
14             search(a,used,path,result);
15             path.removeLast();used[i]=false;
16         }
17     }
18     public static List<List<Integer>> permute(int[] nums) {
19         int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
20     }
21     public static List<List<Integer>> baseline(int[] nums) {
22         int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
23         for(int value:a){List<List<Integer>> next=new ArrayList<>();for(List<Integer> row:rows)for(int at=0;at<=row.size();at++){List<Integer> copy=new ArrayList<>(row);copy.add(at,value);next.add(copy);}rows=next;}
24         Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
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
[]
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
[[]]

Test the contract

Input: All equal values
Output: one full-length row
Multiplicity remains, symmetric branches disappear.
Input: Two repeated values and a distinct value
Output: multinomial number of unique rows
Checks branch ownership and order.
Input: All ternary arrays through length six
Output: factoradic occurrence coverage after value canonicalization
Independent ranking enumerates labeled orders without the main pruning rule.
Input: Repeated MIN/MAX values
Output: correct signed numeric order
No comparator subtraction or source mutation.
Input: Nine equal values
Output: one independent nine-entry row
Exercises the optimized duplicate-heavy boundary without baseline factorial materialization.

Common mistakes and counterexamples

Only test used[i]

Counterexample: Two copies of 1 produce the same value row through different labeled paths.

Add canonical equal-occurrence ordering before descent.

Skip every equal neighbor

Counterexample: [1,1,2] could never place both 1 values.

Allow the later equal occurrence once its predecessor is already owned.

Forget source ownership while sorting

Counterexample: Duplicate detection should not reorder the caller’s array.

Sort a clone and return independent result lists.

Claim O(nP) for this exact scanning loop

Counterexample: All-equal input has P=1 but scans n flags at n levels.

Count surviving-prefix scans or use the stated O(n²P) safe bound.

Follow-ups

Use a value-frequency map.

At each position choose a distinct value with positive remaining count, decrement, recurse, then restore. This removes equal-occurrence scanning and gives a direct multiset proof. Keep a sorted distinct-value list to preserve output order.

Compute the number of unique permutations.

Use the multinomial n!/∏count!, with exact integer arithmetic or cancellation to avoid intermediate overflow. Counting does not require materializing P rows; enumeration still has Θ(nP) output size.

Find the kth unique multiset permutation.

For each candidate value, decrement its count temporarily and compute the number of completions using the residual multinomial. Skip whole rank blocks, restore counts for rejected choices, and specify exact rank bounds.

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

Self-review

Can I prove why !used[i−1] chooses one occurrence assignment per value row?Can I distinguish occurrence availability from duplicate value output?Can I give an honest prefix-scan bound and explain the frequency-map alternative?

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

Related foundations

Backtracking: choose, recurse, restore

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.