14.4 Permutations

14.4.1 Problem Metadata

14.4.2 Description

Given an array of distinct integers, return all possible lc-permutations.

14.4.3 Examples

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

14.4.4 Constraints

  • 1 <= nums.length <= 8
  • All values are distinct

14.4.5 Solution - Backtracking with Choose-Explore-Unchoose Pattern

14.4.5.1 Walkthrough

This problem uses the 2-dimensional traversal mental model of backtracking (see Pattern 1: Choose-Explore-Unchoose):

  • Outer dimension (recursion parameter): path.size() - controls how many elements we’ve chosen (depth 0 to n)
  • Inner dimension (for-loop): Iterates through all array indices from 0 to nums.length - 1

The backtracking explores a conceptual grid where each row represents depth (number of elements chosen) and each column represents a choice among all n elements. At each depth, we try choosing each element that hasn’t been used yet (checked via path.contains()), recurse to the next depth, then remove it to try other options.

Key mechanism: Build permutations incrementally in a path list. Skip elements already in the path using path.contains(nums[i]). When path size equals array length, we’ve built a complete permutation - add a copy to results and backtrack. This approach eliminates the need for a separate visited array by leveraging the path itself for duplicate detection.

14.4.5.2 Analysis

  • Time Complexity: O(n² × n!) - generating n! permutations, each taking O(n) to copy, plus O(n) for contains() check at each step
  • Space Complexity: O(n) for recursion stack and path list (no separate visited array needed)

14.4.5.3 Implementation Steps

  1. Initialize result list to store all permutations.
  2. Define backtrack(path, nums, result):
    1. Base case: If path.size() == nums.length, add a copy of path to result.
    2. Recursive case: For each index i from 0 to nums.length - 1:
      • Skip if path.contains(nums[i]) (already used)
      • Add nums[i] to path (choose)
      • Recursively call backtrack(path, nums, result) (explore)
      • Remove last element from path (unchoose)
  3. Call backtrack(new ArrayList<>(), nums, result) to start with empty path, then return result.

14.4.5.4 Code - Java

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

private void backtrack(List<Integer> path, int[] nums, List<List<Integer>> result) {
    // Base case: found a complete permutation
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    // Try each element that hasn't been used yet
    for (int i = 0; i < nums.length; i++) {
        // Skip if already in current path
        if (path.contains(nums[i])) {
            continue;
        }

        // Choose: add element to path
        path.add(nums[i]);

        // Explore: recurse to next level
        backtrack(path, nums, result);

        // Unchoose: remove element for next iteration
        path.remove(path.size() - 1);
    }
}

14.4.6 Solution - Backtracking with Visited Array

14.4.6.1 Walkthrough

Build lc-permutations by exploring each number once per path. Maintain a visited array so each value appears once per permutation. When the path length equals nums.length, add a copy to the results and backtrack.

14.4.6.2 Analysis

  • Time Complexity: O(n ? n!)
  • Space Complexity: O(n) recursion + visited state

14.4.6.3 Implementation Steps

  1. Initialize result and visited array.
  2. Define backtrack(path):
    1. If path.size() == nums.length, append copy to result.
    2. Otherwise iterate indices:
      • Skip if visited.
      • Mark visited, append value, recurse, then undo.
  3. Call backtrack(new ArrayList<>()) and return result.

14.4.6.4 Code - Java

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {
    boolean[] visited = new boolean[nums.length];
    backtrack(new ArrayList<>(), nums, visited);
    return result;
}

private void backtrack(List<Integer> path, int[] nums, boolean[] visited) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        path.add(nums[i]);
        backtrack(path, nums, visited);
        path.remove(path.size() - 1);
        visited[i] = false;
    }
}