Definition
Permutations generates all n! orderings of n distinct elements using backtracking.
- Choose an unused element and add it to the current partial permutation.
- Explore by recursing to fill the next position with the remaining elements.
- Unchoose by removing the element and clearing its used flag so sibling branches start clean.
- Base case is reached when the current permutation holds all n elements, and a defensive copy is stored.
- Used array is a boolean array parallel to the input that tracks which elements are already placed.
At National Bank of India, a batch of three payments from Rajesh must be tried in every possible processing order to stress-test the settlement engine. We build an order one slot at a time: for the first slot we try each payment, for the next slot each remaining payment, and so on, undoing each choice to explore the next. When all slots are filled we have one complete ordering to test.
Understanding the Concepts
What is the Permutations Problem?
Permutations asks you to generate every possible ordering of a set of distinct elements. For n elements, there are n! (n factorial) permutations. This is one of the most fundamental backtracking problems.
At National Bank of India, Rajesh needs to stress-test the settlement engine by replaying a batch of payments in every possible order.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class PermutationGenerator {
public static 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 static void backtrack(int[] nums, boolean[] used,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current)); // defensive copy
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
current.add(nums[i]);
backtrack(nums, used, current, result);
current.remove(current.size() - 1); // unchoose
used[i] = false;
}
}
public static void main(String[] args) {
int[] paymentIds = {1001, 1002, 1003};
List<List<Integer>> orders = permute(paymentIds);
System.out.println("Total orderings: " + orders.size());
for (List<Integer> order : orders) {
System.out.println(order);
}
}
}
Total orderings: 6
[1001, 1002, 1003]
[1001, 1003, 1002]
[1002, 1001, 1003]
[1002, 1003, 1001]
[1003, 1001, 1002]
[1003, 1002, 1001]
Why Does This Problem Matter?
Permutation generation is the basis for brute-force solutions to ordering problems: scheduling, arrangement, and optimization. Many interview problems reduce to finding the best permutation or checking all permutations.
In banking, the order in which transactions are processed can affect overdraft fees, hold releases, and final balances. Testing every order ensures the system produces consistent results regardless of sequence.
package com.bank.service;
import java.math.BigDecimal;
public class OrderSensitiveSettlement {
public static BigDecimal settle(int[] paymentOrder, BigDecimal startBalance) {
BigDecimal balance = startBalance;
for (int payment : paymentOrder) {
balance = balance.subtract(new BigDecimal(payment));
if (balance.compareTo(BigDecimal.ZERO) < 0) {
balance = balance.subtract(new BigDecimal("35")); // overdraft fee
}
}
return balance;
}
}
How Does the Backtracking Technique Work?
The backtracking follows the choose-explore-unchoose pattern. At each recursion level, we loop over all elements, skip used ones, choose one by marking it used and adding it to the current list, recurse to fill the next position, then unchoose by removing it and clearing the used flag.
The discipline is that after every branch, the state is restored exactly so sibling branches start clean.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class BacktrackingExplained {
public static void backtrack(String[] items, boolean[] used,
List<String> current, int depth) {
String indent = " ".repeat(depth);
if (current.size() == items.length) {
System.out.println(indent + "COMPLETE: " + current);
return;
}
for (int i = 0; i < items.length; i++) {
if (used[i]) continue;
System.out.println(indent + "CHOOSE: " + items[i]);
used[i] = true;
current.add(items[i]);
backtrack(items, used, current, depth + 1);
current.remove(current.size() - 1);
used[i] = false;
System.out.println(indent + "UNCHOOSE: " + items[i]);
}
}
public static void main(String[] args) {
String[] payments = {"P1", "P2"};
backtrack(payments, new boolean[2], new ArrayList<>(), 0);
}
}
CHOOSE: P1
CHOOSE: P2
COMPLETE: [P1, P2]
UNCHOOSE: P2
UNCHOOSE: P1
CHOOSE: P2
CHOOSE: P1
COMPLETE: [P2, P1]
UNCHOOSE: P1
UNCHOOSE: P2
How Is This Different from Subsets?
| Aspect | Permutations | Subsets |
|---|---|---|
| Output count | n! orderings | 2^n subsets |
| Order matters | Yes, [1,2] differs from [2,1] | No, {1,2} = {2,1} |
| Element usage | Every element appears exactly once | Each element is included or excluded |
| Technique | Used-array backtracking | Iterative doubling or start-index backtracking |
| Growth rate | Factorial (much faster) | Exponential |
// Subsets: 2^3 = 8 results, order does not matter
// Permutations: 3! = 6 results, order matters
What Are the Rules and Constraints?
The input must contain distinct elements for the basic version. Each element appears exactly once in every permutation. The used array ensures no element is picked twice. The total output is n!, so this is only feasible for small n. For n = 10 there are 3,628,800 permutations, and for n = 12 there are about 479 million.
package com.bank.core;
public class PermutationFeasibility {
public static void main(String[] args) {
long fact = 1;
for (int n = 1; n <= 12; n++) {
fact *= n;
System.out.println(n + "! = " + fact);
}
}
}
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
What About Duplicate Elements?
When the input contains duplicates, the basic approach produces duplicate permutations. The fix is to sort the input first and skip elements that are equal to their predecessor if the predecessor was not used at the same level.
package com.bank.core;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PermutationsWithDuplicates {
public static List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] nums, boolean[] used,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// Skip duplicate at same level
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
used[i] = true;
current.add(nums[i]);
backtrack(nums, used, current, result);
current.remove(current.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
int[] amounts = {100, 100, 200};
System.out.println(permuteUnique(amounts));
}
}
[[100, 100, 200], [100, 200, 100], [200, 100, 100]]
What Are Common Mistakes?
The first common mistake is forgetting the defensive copy. If you add the current list directly to the result without copying, all entries end up pointing to the same empty list after backtracking.
Wrong code:
// WRONG: all entries in result will be empty after backtracking
result.add(current); // adds reference, not a copy
Correct code:
// CORRECT: store a snapshot of the current state
result.add(new ArrayList<>(current)); // defensive copy
The second mistake is forgetting to unchoose. Without restoring the used flag, the element stays permanently marked and later branches cannot use it.
What About the Swap-Based Approach?
An alternative to the used-array approach is the swap-based method. At each position i, swap element i with each element from i to the end, recurse for position i+1, then swap back.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class PermutationsSwap {
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, result);
return result;
}
private static 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 static void swap(int[] arr, int a, int b) {
int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp;
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask these follow-ups:
- Handle duplicates (Permutations II): sort and skip equal siblings as shown above.
- Find the next permutation in lexicographic order: this uses a specific scan-and-swap algorithm.
- Find the k-th permutation directly without generating all of them: use factorial number system.
- Count permutations of a multiset: use the formula n! / (count1! * count2! * ...).
package com.bank.core;
public class PermutationCount {
// Count permutations of a multiset
public static long countDistinctPermutations(int[] freq) {
int total = 0;
for (int f : freq) total += f;
long numerator = factorial(total);
long denominator = 1;
for (int f : freq) denominator *= factorial(f);
return numerator / denominator;
}
private static long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) result *= i;
return result;
}
}
Visual Overview
Backtracking Tree for [P1, P2, P3]:
[]
┌──────────┼──────────┐
P1 P2 P3
│ │ │
[P1] [P2] [P3]
┌──┐ ┌──┐ ┌──┐
P2 P3 P1 P3 P1 P2
│ │ │ │ │ │
[P1 [P1 [P2 [P2 [P3 [P3
P2 P3 P1 P3 P1 P2
P3] P2] P3] P1] P2] P1]
6 leaf nodes = 3! = 6 permutations
Choose-Explore-Unchoose Pattern: ┌─────────────────────────┐ │ for each unused element │ │ ┌──────────────┐ │ │ │ CHOOSE: │ │ │ │ mark used │ │ │ │ add to list │ │ │ └──────┬───────┘ │ │ ▼ │ │ ┌──────────────┐ │ │ │ EXPLORE: │ │ │ │ recurse │ │ │ └──────┬───────┘ │ │ ▼ │ │ ┌──────────────┐ │ │ │ UNCHOOSE: │ │ │ │ remove │ │ │ │ clear used │ │ │ └──────────────┘ │ └─────────────────────────┘
Key Takeaway
Permutations generates every ordering of a set of distinct elements, and there are n factorial of them. I use backtracking that fills the permutation one position at a time. I keep a current partial ordering and a boolean used array that marks which elements are already placed. At each level I loop over all elements, skip the used ones, and for each available element I choose it by adding it and marking it used, recurse to fill the next position, then unchoose by removing it and clearing the used flag so the next sibling choice can be explored.
The discipline I emphasize is choose, explore, unchoose, with the state restored exactly after every branch so sibling branches start clean. Because the elements are distinct, I do not need any duplicate skipping. If there were duplicates I would sort and skip equal siblings at the same level. I also state plainly that the number of permutations grows factorially, so this is only practical for small inputs.
At National Bank of India I used this to stress-test the settlement engine, which had to settle a batch of distinct payments correctly regardless of processing order, so we replayed every ordering of the batch through the engine. I generated the orderings with backtracking and a used array, storing each full ordering as a fresh copy.
The two alternatives worth knowing are the swap-based approach, which avoids the used array by swapping elements into position, and the next-permutation algorithm, which generates the lexicographic successor without storing all permutations.
Remember one sentence: fill positions one at a time with unused elements, recurse, then undo the choice to explore all n factorial orderings.
---