DSA-120 · FOCUSED PRACTICE

Permutations

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return every permutation of a distinct-value integer array. Each result uses every input value exactly once, and different orders are different answers.

nums is nonnull with at most nine distinct signed int values. Null throws NullPointerException; too many values or any duplicate throws IllegalArgumentException before enumeration. Validation sorts a private copy, so failure also preserves nums.
permute returns numeric lexicographic order. Empty input returns [[]], the single empty arrangement. Each nonempty row has length n and contains exactly the input multiset. This distinct-value API rejects duplicates; DSA-121 handles them.
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: [3,1,2]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
The private sorted copy determines traversal order; nums remains [3,1,2].
Input: []
Output: [[]]
There is exactly one way to arrange no values.
Input: [7]
Output: [[7]]
A full-length leaf emits once.

Before you start

Choice, recursive exploration, and exact undo
Factorial output size and mutable path snapshots

Recognize the structure

Subsets use a start frontier to suppress reordered choices. Here reordering is the objective, so every depth may consider every input position. Only positions already present in the current path are forbidden. A path becomes an answer when all positions are owned, not at every intermediate entry.

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

Self-review

Can I show that used and path describe exactly the same active indices?Can I explain why a subset frontier would lose permutations?Can I separate Θ(n·n!) output cost from O(n) live search workspace?

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

Try before revealing

Hint 1

Each next position can use any input occurrence absent from the active path.

Hint 2

Keep a used array whose true positions match the path exactly.

Hint 3

At full length copy the path; otherwise choose, mark, recurse, and undo both changes.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Insert each new value into every earlier arrangement

Begin with one empty row. For each sorted input value, create a fresh row for every insertion position in every current row. This generates all labeled arrangements, then a lexicographic TreeSet orders them. With distinct values the set removes nothing. The baseline is iterative and compiling, but can retain whole factorial-size generations before the final return.

Improve the baseline

Separate values from availability

Clone and sort the input, reject equal adjacent values, and allocate used[n]. At depth d, path holds d distinct occurrences and used identifies precisely those positions. The remaining values may appear in any next order.

Explore each available next occurrence

Loop over all sorted indices at every frame. Skip used positions; otherwise mark used[i], append a[i], and recurse. Reusing start=i+1 would incorrectly produce combinations rather than permutations.

Emit at full length and restore both state pieces

Only when path.size()==n copy the row. After a child returns, remove its last path value and reset its used flag before trying the next candidate. These two changes are one ownership decision and must be undone together. Ascending values at every first difference give lexicographic order.

Why it is correct

Prefix soundness

At every entry, used flags and path describe the same set of distinct input positions. Choosing a free position preserves uniqueness, and undo restores the parent invariant. A full-length path therefore contains every input value once.

Completeness

Take any target permutation. Its first value corresponds to one available input index; the root loop chooses it. Inductively its next unused index is tried at the next depth. Thus every target arrangement determines a reachable complete path.

Uniqueness and termination

Two distinct root-to-leaf index sequences differ at their first different position and, because values are distinct, produce different rows. Every recursive step consumes one free index, so depth is bounded by n. Sorting and ascending choices establish the promised 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);for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct values required");return a;
    }
    private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
    private static void search(int[] a,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;
            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

A used bit belongs to one active branch

used is not a record of values ever encountered. On [1,2], the first branch owns 1 while exploring [1,2]; after return, 1 becomes available to the separate branch [2,1].

Do not emit partial arrangements

Unlike subsets, [1] is not an answer for input [1,2]. The only emission site is the full-length base case. Empty input meets that base case immediately and must produce one empty row.

The output dominates runtime

Backtracking organizes the traversal and uses small live workspace, but it still copies n values into each of n! rows. The baseline’s generation-based storage is a different memory tradeoff, not evidence that factorial output can be avoided.

Complexity

For n≥1 the main traversal takes Θ(n·n!) time including copying the n! rows. The number of partial distinct permutations is O(n!), and each internal frame scans n availability slots. Output uses Θ(n·n!) element/list storage. Sorted copy, used flags, path and recursive depth use O(n) auxiliary space; n=0 costs constant work and output.

Insertion generation plus lexicographic TreeSet ordering has a safe O((n+1)(n!+1)log(n!+2)+n log(n+1)) time bound, since comparisons can inspect n values. It can retain entire current/next generations and set nodes, using O((n+1)(n!+1)) storage in addition to small scalar state; excluding the eventual returned rows does not reduce its auxiliary bound to O(n).

Exact-state walkthroughs

Reveal normal and boundary traces

Undo makes an earlier value available to a later sibling

Input: [2,1] · Complete distinct permutations: [[1,2],[2,1]]

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

Permutations — path-local occurrence ownership

Phase: initial.

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

Sorted occurrence positions — equal values still have separate supply

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

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	`[2,1]`
sorted	`[1,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);for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct values required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,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             used[i]=true;path.add(a[i]);
13             search(a,used,path,result);
14             path.removeLast();used[i]=false;
15         }
16     }
17     public static List<List<Integer>> permute(int[] nums) {
18         int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
19     }
20     public static List<List<Integer>> baseline(int[] nums) {
21         int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
22         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;}
23         Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
24     }
25 }
26

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]
sorted
[1,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,1]
sorted
[1,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,1]
sorted
[1,2]
path
[1]
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,1]
sorted
[1,2]
path
[1]
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,1]
sorted
[1,2]
path
[1]
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,1]
sorted
[1,2]
path
[1,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,1]
sorted
[1,2]
path
[1,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,1]
sorted
[1,2]
path
[1,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
[[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
[2,1]
sorted
[1,2]
path
[1,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
[[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
[2,1]
sorted
[1,2]
path
[1]
chosenIndices
[0]
used
[true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,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,1]
sorted
[1,2]
path
[1]
chosenIndices
[0]
used
[true,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[1,2]]
phase
"leave"
Undo exactly this choice before the next sibling.
Restoration recovers the parent’s path and availability. Stored output rows remain snapshots, not references to this mutable path.
input
[2,1]
sorted
[1,2]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[1,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]
sorted
[1,2]
path
[2]
chosenIndices
[1]
used
[false,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[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
[2,1]
sorted
[1,2]
path
[2]
chosenIndices
[1]
used
[false,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,2]]
phase
"enter"
Choose one eligible occurrence.
A permutation claims a free position. A one-use combination/subset advances to i+1; reusable candidates recurse from i while strictly reducing the positive remaining sum.
input
[2,1]
sorted
[1,2]
path
[2,1]
chosenIndices
[1,0]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[1,2]]
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]
sorted
[1,2]
path
[2,1]
chosenIndices
[1,0]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[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]
sorted
[1,2]
path
[2,1]
chosenIndices
[1,0]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[1,2],[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
[2,1]
sorted
[1,2]
path
[2,1]
chosenIndices
[1,0]
used
[true,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[1,2],[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
[2,1]
sorted
[1,2]
path
[2]
chosenIndices
[1]
used
[false,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[1,2],[2,1]]
phase
"undo"
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
[2,1]
sorted
[1,2]
path
[2]
chosenIndices
[1]
used
[false,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1},{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,2],[2,1]]
phase
"skip-used"
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,1]
sorted
[1,2]
path
[2]
chosenIndices
[1]
used
[false,true]
frames
[{"start":0,"remaining":null,"next":2,"choice":1}]
rows
[[1,2],[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
[2,1]
sorted
[1,2]
path
[]
chosenIndices
[]
used
[false,false]
frames
[{"start":0,"remaining":null,"next":2,"choice":null}]
rows
[[1,2],[2,1]]
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,1]
sorted
[1,2]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[[1,2],[2,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
[2,1]
sorted
[1,2]
path
[]
chosenIndices
[]
used
[false,false]
frames
[]
rows
[[1,2],[2,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,2],[2,1]]

The unique empty arrangement

Input: [] · Complete distinct 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.

Permutations — path-local occurrence ownership

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);for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct values required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,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             used[i]=true;path.add(a[i]);
13             search(a,used,path,result);
14             path.removeLast();used[i]=false;
15         }
16     }
17     public static List<List<Integer>> permute(int[] nums) {
18         int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
19     }
20     public static List<List<Integer>> baseline(int[] nums) {
21         int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
22         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;}
23         Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
24     }
25 }
26

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
[[]]

A single value reaches the leaf immediately

Input: [7] · Complete distinct permutations: [[7]]

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

Permutations — path-local occurrence ownership

Phase: initial.

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

Sorted occurrence positions — equal values still have separate supply

index 0: 7available

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	`[7]`
sorted	`[7]`
path	`[]`
chosenIndices	`[]`
used	`[false]`
frames	`[]`
rows	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static int[] sorted(int[] nums) {
 4         Objects.requireNonNull(nums,"nums");if(nums.length>9)throw new IllegalArgumentException("materialization limit");
 5         int[] a=nums.clone();Arrays.sort(a);for(int i=1;i<a.length;i++)if(a[i]==a[i-1])throw new IllegalArgumentException("distinct values required");return a;
 6     }
 7     private static int compare(List<Integer> a,List<Integer> b){for(int i=0;i<Math.min(a.size(),b.size());i++){int c=Integer.compare(a.get(i),b.get(i));if(c!=0)return c;}return Integer.compare(a.size(),b.size());}
 8     private static void search(int[] a,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             used[i]=true;path.add(a[i]);
13             search(a,used,path,result);
14             path.removeLast();used[i]=false;
15         }
16     }
17     public static List<List<Integer>> permute(int[] nums) {
18         int[] a=sorted(nums);List<List<Integer>> result=new ArrayList<>();search(a,new boolean[a.length],new ArrayList<>(),result);return result;
19     }
20     public static List<List<Integer>> baseline(int[] nums) {
21         int[] a=sorted(nums);List<List<Integer>> rows=new ArrayList<>();rows.add(new ArrayList<>());
22         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;}
23         Set<List<Integer>> ordered=new TreeSet<>(Solution::compare);ordered.addAll(rows);return new ArrayList<>(ordered);
24     }
25 }
26

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
[7]
sorted
[7]
path
[]
chosenIndices
[]
used
[false]
frames
[]
rows
[]
phase
"initial"
Enter a search state with its next-choice frontier.
A frame describes suspended loop work. At entry, chosen indices and used flags describe exactly the active choices; a just-chosen child path can temporarily be one level ahead before its enter step.
input
[7]
sorted
[7]
path
[]
chosenIndices
[]
used
[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
[7]
sorted
[7]
path
[7]
chosenIndices
[0]
used
[true]
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
[7]
sorted
[7]
path
[7]
chosenIndices
[0]
used
[true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"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
[7]
sorted
[7]
path
[7]
chosenIndices
[0]
used
[true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0},{"start":0,"remaining":null,"next":0,"choice":null}]
rows
[[7]]
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
[7]
sorted
[7]
path
[7]
chosenIndices
[0]
used
[true]
frames
[{"start":0,"remaining":null,"next":1,"choice":0}]
rows
[[7]]
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
[7]
sorted
[7]
path
[]
chosenIndices
[]
used
[false]
frames
[{"start":0,"remaining":null,"next":1,"choice":null}]
rows
[[7]]
phase
"undo"
candidate
0
Return to the caller’s suspended loop.
The caller still owns its selected occurrence until its separate undo step. Root return leaves no active choices or frames.
input
[7]
sorted
[7]
path
[]
chosenIndices
[]
used
[false]
frames
[]
rows
[[7]]
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
[7]
sorted
[7]
path
[]
chosenIndices
[]
used
[false]
frames
[]
rows
[[7]]
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
[[7]]

Test the contract

Input: Empty and one-value inputs
Output: one row each
Checks the full-length base case.
Input: Unsorted distinct signed values
Output: all rows in numeric lexicographic order
Input order remains unchanged.
Input: MIN, zero, MAX
Output: six correctly ordered rows
Sorting avoids subtracting signed values.
Input: Shuffled inputs through length seven
Output: exact factoradic coverage
The independent oracle uses rank decomposition, not recursive used flags.
Input: Nine distinct values
Output: 362,880 independent rows
The enforced boundary has unavoidable factorial output.

Common mistakes and counterexamples

Carry a monotonically increasing start index

Counterexample: [2,1] becomes unreachable after starting with 2.

At each depth scan every currently unused position.

Forget to reset used after recursion

Counterexample: The second sibling has no remaining choices.

Undo the path value and matching ownership flag together.

Emit every prefix

Counterexample: For [1,2], partial rows [1] and [] are not full arrangements.

Emit only at depth n; retain the empty-input convention.

Use this distinct-value API for duplicates

Counterexample: [1,1] would have two labeled paths for one value sequence.

Reject duplicates here or apply DSA-121’s canonical equal-occurrence rule.

Follow-ups

Allow duplicate values.

Sort a clone and suppress the later equal occurrence while its preceding equal copy is unused. Merely checking used[i] only prevents occurrence reuse; it does not prevent equivalent value permutations.

Return the kth permutation without enumerating all earlier answers.

For distinct values, factorial block sizes identify the next selected rank among remaining values. Define zero/one-based k and detect factorial overflow; this factoradic idea also supplies an independent bounded oracle.

Enumerate in place by swaps.

Define a fixed prefix and swap each remaining value into the next position, then swap back. If caller mutation is forbidden, clone first. Lexicographic order is not automatic, and the output still needs independent snapshots.

Related foundations

Backtracking: choose, recurse, restore

Keep practicing

Return to the lesson

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