Permutations

1. Introduction: The Art of Arrangement

Imagine you have three colored blocks: Red, Green, and Blue. How many different ways can you line them up on a table? You could do RGB, RBG, GRB, GBR, BRG, or BGR. You just generated all possible Permutations of those three blocks.

In computer science, generating permutations is a classic combinatorial problem. It frequently appears in technical interviews and is the foundation for solving complex constraint-satisfaction problems, like the Traveling Salesperson Problem (checking every possible route).

Unlike combinations (where order doesn't matter, and [1, 2] is identical to [2, 1]), in permutations, order matters. Every unique arrangement of the same set of elements is considered a valid, distinct permutation.

2. Core Concept: Backtracking for Permutations

The Decision Tree

To generate permutations of an array of size $N$, we can build a decision tree:

1. Level 1: We have $N$ choices for the first position.
2. Level 2: We have $N-1$ choices for the second position (since we can't reuse the element we just picked).
3. Level 3: We have $N-2$ choices, and so on...
4. Leaves: The leaf nodes represent complete permutations of length $N$. There will be exactly $N!$ (N factorial) leaf nodes.

State Tracking

Since we cannot reuse elements in a single permutation, we must track which elements are currently "in use". We have two main ways to do this:

1. Visited Array: Maintain a boolean[] visited array of the same size as the input. If visited[i] is true, we skip it.
2. Swapping In-Place: Instead of a visited array, we can swap elements in the original array to partition it into "used" and "unused" sections. This saves $O(N)$ auxiliary space!

3. Beginner Code Example: All Permutations (Visited Array)

Problem Statement: (LeetCode 46) Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

import java.util.ArrayList;
import java.util.List;

public class PermutationsBasic {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // boolean array defaults to false
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }
    
    private static void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] visited) {
        // Base Case: If the current permutation is the same size as nums, it's complete!
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current)); // Deep copy!
            return;
        }
        
        // Explore all possible choices
        for (int i = 0; i < nums.length; i++) {
            // Pruning: If the number is already used in this permutation, skip it
            if (visited[i]) continue;
            
            // MAKE CHOICE
            visited[i] = true;
            current.add(nums[i]);
            
            // RECURSE
            backtrack(result, current, nums, visited);
            
            // UNDO CHOICE (Backtrack)
            current.remove(current.size() - 1);
            visited[i] = false;
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(N \times N!)$. There are $N!$ permutations. For each permutation, we spend $O(N)$ time deep-copying the list into the result.
• Space Complexity: $O(N)$. The recursion stack depth is $N$, the current list size is $N$, and the visited array size is $N$.

4. Intermediate Code Example: Unique Permutations (Handling Duplicates)

Problem Statement: (LeetCode 47) Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

If the input is [1, 1, 2], naive backtracking generates duplicate identical permutations because it treats the first 1 and the second 1 as completely different items.

The Fix:

1. Sort the array first! This groups duplicates together.
2. In the loop, if the current number is the same as the previous number (nums[i] == nums[i-1]), and the previous number was NOT used in this current depth (!visited[i-1]), skip it! This forces the algorithm to use duplicate numbers in a strictly enforced left-to-right order, preventing identical branches.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationsUnique {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 1. Sort to group duplicates
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }
    
    private static void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] visited) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            
            // 2. Pruning Duplicates!
            // If it's a duplicate AND the previous identical element was NOT used
            // in this specific branch, we skip to avoid generating a duplicate permutation.
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            
            visited[i] = true;
            current.add(nums[i]);
            backtrack(result, current, nums, visited);
            current.remove(current.size() - 1);
            visited[i] = false;
        }
    }
}

Time & Space: Still mathematically $O(N \times N!)$ in the absolute worst case where all elements are distinct, but drastically faster in practice due to heavy duplicate pruning.

5. Advanced Code Example: Next Permutation (In-Place Array Math)

Problem Statement: (LeetCode 31) Implement nextPermutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible (it's sorted in descending order), rearrange it to the lowest possible order (ascending). Do it in $O(1)$ extra memory.

This is NOT a backtracking problem; it's a math/array problem that is famously asked to see if you understand the internal mechanics of permutation generation.

Step-by-step trace for [1, 3, 5, 4, 2]:

1. Find the dip: Iterate backwards. Find the first element that is smaller than the element directly after it. (Here, 3 is smaller than 5). Index i = 1.
2. Find the next largest: Iterate backwards again. Find the first element strictly greater than the dip element 3. (Here, 4 is greater than 3). Index j = 3.
3. Swap: Swap nums[i] and nums[j]. Array becomes [1, 4, 5, 3, 2].
4. Reverse the suffix: The elements after i ([5, 3, 2]) are guaranteed to be in descending order. Reverse them to make them ascending [2, 3, 5]. Final array: [1, 4, 2, 3, 5].

public class NextPermutation {
    public static void nextPermutation(int[] nums) {
        // Step 1: Find the dip
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // If i < 0, the entire array is descending (e.g., 5, 4, 3, 2, 1)
        // It is the LAST permutation. We skip step 2 & 3 and just reverse it.
        if (i >= 0) {
            // Step 2: Find the next largest
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // Step 3: Swap
            swap(nums, i, j);
        }
        
        // Step 4: Reverse the descending suffix
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private static void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We do a maximum of three passes over the array (find dip, find swap, reverse).
• Space Complexity: $O(1)$. Fully in-place.

6. Common Mistakes Beginners Make

1. Forgetting !visited[i-1] in the duplicate check

   • The Mistake: Writing if (i > 0 && nums[i] == nums[i-1]) continue;
   • Why it's wrong: This entirely bans using identical numbers in the same permutation. For input [1, 1, 2], it would be impossible to output [1, 1, 2], because when it tries to add the second 1, it sees the previous element is 1 and skips it. The !visited[i-1] ensures we only skip if the previous identical element was bypassed at the current level, not if it's currently in use by a parent node!

2. Using $O(N)$ contains() checks instead of a visited array

   • The Mistake: if (current.contains(nums[i])) continue;
   • Why it's wrong: ArrayList.contains() takes $O(N)$ time. Since you do this $N$ times inside a recursion tree of size $N!$, your time complexity explodes from $O(N!)$ to $O(N \cdot N!)$. A boolean[] visited does the check in $O(1)$.

3. Not deep copying the list in the base case

   • The Mistake: result.add(current);
   • The Fix: result.add(new ArrayList<>(current));

7. Interview Q&A

Q1: How do you generate permutations without using a visited array to save memory? Answer: We can use the Swapping Pattern. At level index of the recursion, we loop i from index to N-1. We swap nums[index] with nums[i], recurse for index + 1, and then swap them back. This partitions the array into "fixed" elements on the left, and "unfixed" elements on the right. This drops auxiliary space to just $O(N)$ for the recursion stack!

Q2: Can we use a bitmask instead of a boolean[] visited array? Answer: Yes! If the array size is $\le 32$, we can pass an integer mask through the recursion. if ((mask & (1 << i)) != 0) checks if visited. mask | (1 << i) marks it visited. This is slightly faster due to bitwise operations.

Q3: Is generating all permutations of an array of size 20 feasible? Answer: No! $20!$ is roughly $2.43 \times 10^{18}$. Even if a computer processes a billion operations per second, it would take over 77 years to finish. Anything above $N=12$ is generally guaranteed to TLE (Time Limit Exceeded) in competitive programming.

8. Practice Problems

1. Permutations (LeetCode 46)
   • Goal: Implement the standard visited array approach.
2. Permutations II (LeetCode 47)
   • Goal: Implement the duplicate handling logic.
3. Next Permutation (LeetCode 31)
   • Goal: Implement the $O(N)$ math/array reversal approach without using recursion.

9. Summary

• Permutations generate all possible orderings of a dataset. Order matters.
• Time Complexity is inherently $O(N!)$, meaning it is only viable for very small constraints ($N \le 12$).
• State Tracking is required to prevent reusing elements. Use a boolean[] visited array or in-place array swapping.
• Duplicate Handling requires sorting the input first, and applying the nums[i] == nums[i-1] && !visited[i-1] pruning logic.
• Next Permutation is a specific array-manipulation pattern involving finding a dip, swapping, and reversing the suffix.