Definition
- Permutation – an arrangement of all elements of a set in a specific order. Order matters.
- Count – n distinct elements have n! (n factorial) permutations.
- Used-marker – a boolean array tracks which elements are in the current arrangement to prevent repetition within a single permutation.
- Recording – only at leaves (when path length equals n), because a permutation must use all elements.
- Swap variant – permutes the array in place without a used-array by swapping elements into the current position.
- Complexity – O(n * n!) time and space.
Imagine the National Bank of India must try every possible processing order of a small batch of urgent transfers to find the sequence that best satisfies liquidity rules. A clerk fills a row of slots, one per transfer. In each slot she tries each remaining transfer, then moves to the next slot, systematically producing every ordering without repeating a transfer within one arrangement.
Understanding the Concepts
What is the Permutations problem?
Given n distinct elements, generate all possible orderings (permutations). Unlike subsets where order does not matter and not all elements are used, a permutation uses every element exactly once in a specific order.
This is LeetCode 46.
package com.bank.service;
// Input: [1, 2, 3]
// Permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
// Count: 3! = 6
How does the used-marker approach work?
Carry a running path and a boolean used array parallel to the input. At each call, if the path length equals n, record a copy. Otherwise loop over all elements, skip any already used, and for each unused one mark it used, add it to the path, recurse, then unmark and remove.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] used,
List<Integer> path,
List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path)); // record at leaf
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // skip used elements
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
Permutations solver = new Permutations();
System.out.println(solver.permute(new int[]{1, 2, 3}));
}
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
How does the in-place swap variant work?
Instead of a used-array, swap elements into the current position. For position start, swap nums[start] with each nums[i] where i >= start, recurse with start + 1, then swap back.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class PermutationsSwap {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, result);
return result;
}
private void backtrack(int[] nums, int start,
List<List<Integer>> result) {
if (start == nums.length) {
List<Integer> perm = new ArrayList<>();
for (int n : nums) perm.add(n);
result.add(perm);
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
backtrack(nums, start + 1, result);
swap(nums, start, i); // swap back
}
}
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
public static void main(String[] args) {
PermutationsSwap solver = new PermutationsSwap();
System.out.println(solver.permute(new int[]{1, 2, 3}));
}
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
How is this different from subsets?
| Feature | Subsets | Permutations |
|---|---|---|
| Uses all elements | No, any subset of them | Yes, all n |
| Order matters | No | Yes |
| Decision per step | Include or exclude | Which unused element here |
| Record when | Every recursive call | Only at leaves (full length) |
| Count | 2^n | n! |
How do you handle duplicates (Permutations II)?
For inputs with repeated elements (LeetCode 47), sort first and skip a candidate when it equals the previous one and the previous one is not used. This avoids generating identical permutations.
package com.bank.service;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PermutationsWithDuplicates {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] used,
List<Integer> path,
List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // skip dup
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
PermutationsWithDuplicates solver = new PermutationsWithDuplicates();
System.out.println(solver.permuteUnique(new int[]{1, 1, 2}));
}
}
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
What are the edge cases?
- Single element: one permutation,
[element]. - Two elements: two permutations.
- Large n: n! grows extremely fast. n = 10 gives 3.6 million permutations.
package com.bank.service;
public class PermEdgeCases {
public static void main(String[] args) {
Permutations solver = new Permutations();
System.out.println("Single: " + solver.permute(new int[]{5}));
System.out.println("Two: " + solver.permute(new int[]{1, 2}));
}
}
Single: [[5]]
Two: [[1, 2], [2, 1]]
What about the banking domain use case?
At the National Bank of India, treasury occasionally evaluates every possible processing order of a very small batch of urgent transfers to find the sequence that keeps intraday liquidity within limits. The used-marker ensures each transfer appears exactly once per ordering.
package com.bank.service;
import java.util.List;
public class TransferOrderOptimizer {
public static void main(String[] args) {
int[] transferIds = {101, 102, 103};
Permutations solver = new Permutations();
List<List<Integer>> orders = solver.permute(transferIds);
System.out.println("Processing orders to evaluate: " + orders.size());
for (List<Integer> order : orders) {
System.out.println(" " + order);
}
}
}
Processing orders to evaluate: 6
[101, 102, 103]
[101, 103, 102]
[102, 101, 103]
[102, 103, 101]
[103, 101, 102]
[103, 102, 101]
What are common interview follow-up questions?
- How is this different from subsets? (Order matters, all elements used, record only at leaves, count is n! not 2^n.)
- How do you handle duplicates? (Sort and skip when current equals previous and previous is unused.)
- What is the swap variant? (Swap each element into the current position instead of using a used-array.)
- What is the time complexity? (O(n * n!) because n! permutations are each O(n) to copy.)
- Why is this only feasible for small n? (n! grows faster than exponential.)
Visual Overview
Permutations: [1, 2, 3]
backtrack(path=[], used=[F,F,F])
├── pick 1 → backtrack([1], [T,F,F])
│ ├── pick 2 → backtrack([1,2], [T,T,F])
│ │ └── pick 3 → [1,2,3] ✓
│ └── pick 3 → backtrack([1,3], [T,F,T])
│ └── pick 2 → [1,3,2] ✓
├── pick 2 → backtrack([2], [F,T,F])
│ ├── pick 1 → [2,1,3] ✓
│ └── pick 3 → [2,3,1] ✓
└── pick 3 → backtrack([3], [F,F,T])
├── pick 1 → [3,1,2] ✓
└── pick 2 → [3,2,1] ✓
Total: 3! = 6 permutations
Key Takeaway
A permutation is an arrangement of all elements in a specific order, and n distinct elements have n! permutations. Backtracking generates them by filling one position at a time. At each position you try every unused element, mark it used, recurse to fill the next position, then unmark and remove.
The key differences from subsets are that order matters, all elements must be used, and you record only at leaves when the path is full. A boolean used-array parallel to the input prevents repeating an element within a single arrangement, and the add-mark-recurse-unmark-remove rhythm is the backtracking heartbeat.
For inputs with duplicates, sort first and skip a candidate equal to its predecessor when the predecessor is unused. The swap variant permutes the array in place without a used-array, saving auxiliary space. Both are valid interview answers.
At the National Bank of India, treasury used this to evaluate every processing order of a small batch of urgent transfers, finding the sequence that kept intraday liquidity within limits. The factorial growth means this is only feasible for small n, which is a key point to state.
Remember one sentence: try every unused element at each position, mark and unmark, and record only at full-length leaves.
---