Permutations: The Complete Backtracking Guide

Introduction

A Permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement. Unlike combinations, where order does not matter, permutations are heavily dependent on the sequence.

In the context of coding interviews and algorithms, the problem of generating all permutations is a classic application of the Backtracking technique. It forces you to explore every possible path to find the solution.

Core Concept: The Backtracking Approach

Backtracking is a recursive algorithmic technique where we build a candidate solution incrementally. At each step, we make a choice, and if that choice leads to a valid solution, we keep it. If it leads to an invalid state or a dead end, we "backtrack" (undo the choice) and try a different path.

The Three Steps of Backtracking

Choose: Select an element from the remaining pool to add to the current path.
Explore: Recursively call the function to build upon the current path.
Unchoose (Backtrack): Remove the element from the current path to allow other elements to be chosen in subsequent iterations.

Algorithmic Patterns

There are two primary ways to solve the Permutations problem using backtracking:

Pattern 1: Using a `used` Array (State Management)

This approach is often more intuitive. We maintain a boolean array used to track which numbers have been included in the current permutation path.

Logic:

Iterate through the input array.
If the number at index i is not used, add it to the current path, mark it as used, and recurse.
Once the recursion returns, unmark it as used (backtrack) so it can be used in other permutations.

Pattern 2: In-Place Swapping (Space Optimization)

This approach modifies the input array directly. It is more space-efficient but requires careful handling of the swapping logic.

Logic:

Iterate from the current index i to the end of the array.
Swap the element at i with the element at j.
Recurse with i + 1.
Swap back (undo the swap) to restore the array for the next iteration.

Code Implementation

Approach 1: Using a `used` Array (Recommended for Beginners)

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];
  const used: boolean[] = new Array(nums.length).fill(false);

  function backtrack() {
    // Base Case: If the path length equals the input length,
    // we have a complete permutation.
    if (path.length === nums.length) {
      result.push([...path]); // Push a copy of the path
      return;
    }

    // Recursive Step: Try every number
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // Skip if already used in this path

      // 1. Choose
      path.push(nums[i]);
      used[i] = true;

      // 2. Explore
      backtrack();

      // 3. Unchoose (Backtrack)
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

Approach 2: In-Place Swapping (Space Optimized)

function permute(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number) {
    // Base Case: If start index reaches the end, we have a permutation
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      // Swap current index with start index
      [nums[start], nums[i]] = [nums[i], nums[start]];

      // Recurse for the next position
      backtrack(start + 1);

      // Backtrack: Swap back to restore original array state
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }

  backtrack(0);
  return result;
}

Complexity Analysis

Time Complexity: $O(N imes N!)$

$N!$ (Factorial): There are $N!$ permutations for an array of size $N$. We must generate all of them.
$N$: For each permutation, we copy the array into the result (or construct it), which takes $O(N)$ time.

Space Complexity: $O(N)$

Recursion Stack: The depth of the recursion tree is $N$.
Auxiliary Space: The used array or the recursion stack takes $O(N)$ space.
Output Space: The result array stores $N!$ permutations, each of size $N$. This is technically required output space and is not counted towards auxiliary space complexity in standard Big O analysis.

Handling Duplicates

If the input array contains duplicate numbers (e.g., [1, 1, 2]), the standard backtracking approach will generate duplicate permutations. To fix this, we must skip over duplicate numbers at the same level of recursion.

Optimization Logic:

Sort the array first.
In the loop, if nums[i] == nums[i-1] and !used[i-1], skip it. This ensures we only pick the first occurrence of a duplicate at a specific depth.

// Optimization for duplicates
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
  continue;
}

Common Mistakes to Avoid

Modifying the Input Array Incorrectly: When using the swapping approach, always remember to swap back after the recursive call. If you don't, the array state will be corrupted, and you will generate incorrect permutations.
Not Copying the Path: In the used array approach, always push path.slice() or [...path] to the result. If you push path directly, you are pushing a reference to the same array object, which will be modified by subsequent backtracking steps.
Forgetting the Base Case: The base case is critical. Without it, the recursion will run infinitely until the stack overflows.

Real-World Applications

Cryptography: Generating all possible keys or passwords for brute-force attacks (though usually restricted by time).
Scheduling: Assigning tasks to time slots where the order of tasks matters (e.g., tournament scheduling).
Games: Solving puzzles like the Rubik's Cube or generating all possible moves in a game tree.
Data Analysis: Generating all possible combinations of features for machine learning model testing.

Practice Strategy

Start Simple: Implement the used array approach first to understand the flow of state management.
Optimize: Once comfortable, try the in-place swapping approach to reduce memory overhead.
Edge Cases: Test your function with arrays containing 0, 1, or duplicate elements.
Constraint Handling: Modify the problem to generate only the first $k$ permutations if the input size is very large.

Related Concepts

Combinations: Where order does not matter.
Subsets: A subset is a permutation of a subset.
Permutations II: The variation of this problem involving duplicates.

Permutations - Complete Backtracking Guide