Recursion & BacktrackingMediumO(n! × n) time · O(n) space

Permutations

Mahabharata — Every Battle Order — All Possible Arrangements of the Warriors

n योद्धाओं के सभी क्रम — n! arrangements। अदला-बदली से — प्रत्येक स्थान पर प्रत्येक योद्धा॥

*All arrangements of n warriors — n! permutations. By swapping — each warrior at each position.*

The Story

Generate all permutations of a distinct integer array.

For `nums=[1,2,3]`: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] (6 permutations = 3!).

**Backtracking with swap:** - Fix position `start`, try each element from start..n-1 at this position - Swap nums[start] with nums[i], recurse for next position - Swap back (backtrack)

```java void backtrack(List<List<Integer>> res, int[] nums, int start) { if (start == nums.length) { res.add(Arrays.stream(nums).boxed().collect(Collectors.toList())); return; } for (int i=start; i<nums.length; i++) { swap(nums, start, i); // Choose: put nums[i] at position start backtrack(res, nums, start+1); // Explore: fix remaining positions swap(nums, start, i); // Unchoose: restore original order } } ```

Trace `[1,2,3]`: - start=0: try each of [1,2,3] at position 0 - swap(0,0)=[1,2,3]: backtrack(1) - start=1: swap(1,1)=[1,2,3], swap(1,2)=[1,3,2] → [1,2,3], [1,3,2] - swap(0,1)=[2,1,3]: backtrack(1) → [2,1,3], [2,3,1] - swap(0,2)=[3,2,1]: backtrack(1) → [3,2,1], [3,1,2]

All 6 permutations generated! ✓

**This is the definitive backtracking pattern** — explicit choose (swap in), explore (recurse), unchoose (swap back).

The Insert-at-All-Positions Approach

Insert nums[0] at all positions in each permutation of nums[1..n-1]. Recursive but builds new lists. O(n! × n).

java

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    if (nums.length == 0) { res.add(new ArrayList<>()); return res; }
    int first = nums[0];
    int[] rest = Arrays.copyOfRange(nums, 1, nums.length);
    for (List<Integer> perm : permute(rest))
        for (int i=0;i<=perm.size();i++) {
            List<Integer> p=new ArrayList<>(perm); p.add(i,first); res.add(p);}
    return res;
}

The Swap-Recurse-Swap-Back Wisdom

For each position start: swap nums[start] with nums[i] (i from start..n-1). Recurse for start+1. Swap back. Base: start==n → add current permutation.

java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, nums, 0);
    return res;
}

void backtrack(List<List<Integer>> res, int[] nums, int start) {
    if (start == nums.length) {
        List<Integer> perm = new ArrayList<>();
        for (int n : nums) perm.add(n);
        res.add(perm);
        return;
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);             // Choose
        backtrack(res, nums, start + 1);  // Explore
        swap(nums, start, i);             // Unchoose
    }
}

void swap(int[] nums, int i, int j) { int t=nums[i]; nums[i]=nums[j]; nums[j]=t; }

Step-by-Step Walkthrough

[1]: start=0,i=0. swap=[1]. start=1==n. Add [1]. Return [[1]] ✅

Deep Insight

**Why swap back?** After exploring all permutations with nums[i] at position `start`, we restore the original arrangement so the next iteration `i+1` sees the correct array state.

**n! permutations × n to copy each:** Total O(n! × n) time, which is unavoidable since we're generating all n! permutations each of length n.

**Permutations with duplicates (LeetCode 47):** Before swapping, check if nums[i] was already placed at `start` in a previous iteration (use a set to track). This prunes duplicate permutations.

**This swap pattern vs used-array pattern:** An alternative is using a boolean `used[]` array and a separate path list. Functionally equivalent but the swap pattern is more space-efficient.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n! × n)	O(n! × n)	Build all permutations explicitly
Optimal	O(n! × n)	O(n)	In-place swaps; O(n) call stack; O(n! × n) for output

Pattern Recognition

✅ Permutations = swap-recurse-swap-back
✅ for i from start..n-1: swap(start,i), recurse(start+1), swap(start,i)
✅ n! permutations, O(n) space (excluding output)
✅ With duplicates: skip same value already placed at start

**LeetCode Trigger Phrases:**
→ "permutations" of array
→ Generate all orderings
→ Classic backtracking with swap

Bhagavad Gita 4.5

बहूनि मे व्यतीतानि जन्मानि तव चार्जुन। तान्यहं वेद सर्वाणि न त्वं वेत्थ परन्तप॥

Many births of Mine have passed, and yours too, O Arjuna. I know them all, but you do not, O scorcher of foes.

Connection: The permutation algorithm explores every possible ordering — every arrangement of warriors, every sequence of lives. Like Krishna who knows all past lives and their arrangements while Arjuna remembers only the current one, the algorithm exhaustively generates all n! permutations. Each swap represents a choice of which warrior stands in the current position; the backtrack restores the original order before trying the next arrangement, just as each new life begins from the soul's essential nature.