Permutations Pattern in Backtracking
The Problem
Given distinct items, produce every ordering — every way to line all of them up.
Input: [1, 2, 3] Orderings (3! = 6): [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] Unlike subsets, [1, 2, 3] and [3, 2, 1] are DIFFERENT answers, and every answer uses ALL items exactly once.
Typical disguises: seating guests around a table, scheduling tasks in some order, trying every visiting order for a handful of cities, forming numbers from given digits.
Method 1: Slot-Filling With a Used Array
Fill position 0, then position 1, and so on. At each position, try every element not used yet.
used = [F, F, F], path = []
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
choose: path.append(nums[j]); used[j] = true
explore: recurse
un-choose: path.pop(); used[j] = false
If the input is sorted, this method produces orderings in lexicographic (dictionary) order, which is often a nice bonus.
Method 2: In-Place Swapping
Treat the array itself as the path. Positions 0 … i−1 are already fixed. To fill position i, swap each candidate from i … n−1 into slot i, recurse, then swap back.
fix position 0: swap(0,0) → [1,2,3] recurse on positions 1..2 swap(0,1) → [2,1,3] recurse on positions 1..2 then swap back → [1,2,3] swap(0,2) → [3,2,1] recurse on positions 1..2 then swap back → [1,2,3] No extra path or used array: O(1) extra space besides the call stack. The output order is NOT lexicographic (notice [3,2,1] before [3,1,2]).
Handling Duplicate Values
With [1, 1, 2], naive generation yields 6 orderings, but only 3 are distinct:
naive: [1,1,2] [1,2,1] [1,1,2] [1,2,1] [2,1,1] [2,1,1] distinct: [1,1,2] [1,2,1] [2,1,1] → 3!/2! = 3
The fix for the used-array method:
1. Sort the input so equal values are adjacent.
2. Skip element j when:
nums[j] == nums[j-1] and used[j-1] is false
Meaning: copies of the same value must be used left to right.
If the left copy is still free, using the right copy now would create
an ordering we already produced with the copies swapped.
Tree for sorted [1a, 1b, 2] (✂ = skipped by the rule):
[]
/ | \
[1a] ✂ [1b] [2]
/ \ (1a still free) / \
[1a,1b] [1a,2] [2,1a] ✂[2,1b]
| | |
[1,1,2] [1,2,1] [2,1,1]
Code: Used Array, Swaps, and Duplicates
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Permutations {
// Method 1 — slot-filling with a used array
static void byUsed(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
if (path.size() == nums.length) { out.add(new ArrayList<>(path)); return; }
for (int j = 0; j < nums.length; j++) {
if (used[j]) continue;
used[j] = true; path.add(nums[j]); // choose
byUsed(nums, used, path, out); // explore
path.remove(path.size() - 1); used[j] = false; // un-choose
}
}
// Method 2 — in-place swaps; positions < i are already fixed
static void bySwap(int[] nums, int i, List<List<Integer>> out) {
if (i == nums.length) {
List<Integer> copy = new ArrayList<>();
for (int x : nums) copy.add(x);
out.add(copy);
return;
}
for (int j = i; j < nums.length; j++) {
swap(nums, i, j); // choose: bring nums[j] into slot i
bySwap(nums, i + 1, out); // explore
swap(nums, i, j); // un-choose: swap back
}
}
static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
// Distinct orderings — input must be sorted
static void distinct(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
if (path.size() == nums.length) { out.add(new ArrayList<>(path)); return; }
for (int j = 0; j < nums.length; j++) {
if (used[j]) continue;
if (j > 0 && nums[j] == nums[j - 1] && !used[j - 1]) continue; // copies left to right
used[j] = true; path.add(nums[j]);
distinct(nums, used, path, out);
path.remove(path.size() - 1); used[j] = false;
}
}
static void show(String label, List<List<Integer>> perms) {
StringBuilder sb = new StringBuilder(label + " (" + perms.size() + "):");
for (List<Integer> p : perms) sb.append(" ").append(p);
System.out.println(sb);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> a = new ArrayList<>(), b = new ArrayList<>();
byUsed(nums, new boolean[3], new ArrayList<>(), a);
bySwap(nums, 0, b);
show("used-array", a);
show("swapping ", b);
int[] dup = {2, 1, 1};
Arrays.sort(dup);
List<List<Integer>> naive = new ArrayList<>(), unique = new ArrayList<>();
byUsed(dup, new boolean[3], new ArrayList<>(), naive);
distinct(dup, new boolean[3], new ArrayList<>(), unique);
show("dup naive ", naive);
show("distinct ", unique);
}
}Output:
used-array (6): [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
swapping (6): [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]
dup naive (6): [1, 1, 2] [1, 2, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [2, 1, 1]
distinct (3): [1, 1, 2] [1, 2, 1] [2, 1, 1]
The swapping method produces the same six orderings, but [3, 2, 1] comes before [3, 1, 2] — swapping does not preserve sorted order.
Partial Arrangements: k Out of n
Sometimes only k positions need filling — for example, awarding gold, silver, and bronze among 5 finalists. Use the used-array method and stop at length k.
count = n × (n-1) × ... × (n-k+1) = n! / (n-k)!
n = 5, k = 3 (podium): 5 × 4 × 3 = 60 arrangements
n = 4, k = 2: 4 × 3 = 12 arrangements
Change only the base case:
if len(path) == k:
record
return
Adding Rules While Building
Ordering problems usually come with constraints. Check them at the moment an element is placed:
"No two adjacent values may differ by more than 2"
→ before placing nums[j], check |nums[j] - path[-1]| ≤ 2
"Task B must come after task A"
→ allow B only if A is already used
"The arrangement must form a valid number (no leading zero)"
→ at position 0, skip the digit 0
Each check removes a whole subtree of (n - depth)! orderings at once.
Used Array vs Swapping
| Used array | Swapping | |
|---|---|---|
| Extra memory | path + used[] (O(n)) | none beyond the stack |
| Output order | lexicographic if input sorted | not sorted |
| Duplicate handling | simple sort + skip rule | needs a per-level "seen" set |
| Partial (k of n) | change base case | stop at depth k, copy prefix |
| Constraint checks | easy — path is explicit | easy — prefix is nums[0..i-1] |
For interviews, the used-array version is usually clearer and handles duplicates more cleanly.
Common Mistakes
Using a start index. That generates groups, not orderings — [2, 1] is never produced.
Forgetting to reset used[j]. After one branch, the element stays marked as used and disappears from every later ordering.
Wrong duplicate condition. !used[j-1] is the standard form. The variant used[j-1] also produces each ordering once, but prunes much later and explores far more nodes. Leaving the condition out entirely gives repeated orderings.
Swapping without swapping back. The array drifts away from its original state and some orderings are skipped while others repeat.
Interview Questions
Q: What is the time complexity of generating all orderings of n items?
There are n! orderings and each one is copied in O(n), so O(n · n!). The search tree has about e · n! nodes, which is within a constant factor of the leaf count. Auxiliary space is O(n) for the stack, path, and used array.
Q: Explain the duplicate-skipping condition in your own words.
After sorting, equal values sit side by side. We insist that identical copies are always placed in the same relative order as in the sorted input. If the earlier copy is still unused, placing the later copy now would break that order, and the resulting ordering would duplicate one we build when the copies are in order — so we skip it.
Q: How would you generate only the k-th ordering in lexicographic order without listing all of them?
Use counting instead of search. With n items, each choice for the first position covers (n − 1)! orderings, so the first element is the one at index (k − 1) / (n − 1)! among those remaining. Remove it, reduce k, and repeat. This runs in O(n²) with a list, or O(n log n) with a better structure.
Summary
- ›n distinct items have n! orderings; listing them costs O(n · n!).
- ›Used array: loop from 0, skip used elements — clear, lexicographic, easy to deduplicate.
- ›Swapping: fix slot i by swapping candidates into it, then swap back — no extra memory.
- ›Duplicates: sort, then skip
nums[j] == nums[j-1] && !used[j-1]. - ›k of n: stop at length k → n! / (n − k)! arrangements.
Next, Combination Problems sits between subsets and orderings: choose exactly k items, or choose items that hit a target — with and without reuse.
How many orderings do 5 distinct items have?