Generate Permutations

Given an array of distinct integers, return all permutations — every ordering of the elements. The classic backtracking template builds a path, marks elements with a used array, and backtracks by undoing each choice. This lesson covers the algorithm, swap variant, LeetCode 46/47, and implementations in C, Java, and Python with trace tables.

Overview

A permutation is a rearrangement of all elements. For n distinct items there are n! permutations. Backtracking explores a decision tree: at each level, pick an unused element, go deeper, then undo.

nums = [1, 2, 3] — decision tree (first branch shown)

              []
         /    |    \
        1     2     3
       /|\   /|\   /|\
      2 3   1 3   1 2
      | |   | |   | |
     [1,2,3] ...  [3,2,1]

6 permutations total: 3! = 6

Problem Statement

Input: Array nums of n distinct integers.

Output: All permutations — each is an array containing every element exactly once.

Example: nums = [1, 2, 3] → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Count: For distinct elements, answer size is n!.

Backtracking Algorithm (used + path)

1. Maintain current path (partial permutation) and used[i] flags.
2. Base case: if len(path) == n, append a copy to result.
3. For each index i where used[i] == false:
   • Mark used[i] = true, append nums[i] to path.
   • Recurse.
   • Backtrack: remove last element, set used[i] = false.

Swap Approach

Fix position start and swap nums[start] with each nums[i] where i ≥ start. Recurse on start + 1, then swap back.

• Builds permutations in-place — no separate path list.
• When start == n, record a copy of nums.
• Common in C/C++ interviews; same O(n!) time.

Code (C, Java, Python)

Python

def permute(nums):
    """All permutations — backtracking with used[] and path."""
    n = len(nums)
    used = [False] * n
    path = []
    result = []

    def backtrack():
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result


if __name__ == "__main__":
    print(permute([1, 2, 3]))  # 6 permutations

Java

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

public class Permutations {

    public static void backtrack(int[] nums, boolean[] used, List<Integer> path,
                                 List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

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

    public static void main(String[] args) {
        System.out.println(permute(new int[]{1, 2, 3}).size()); // 6
    }
}

C (swap approach)

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void permute_swap(int nums[], int start, int n, int *count) {
    int i;
    if (start == n) { (*count)++; return; }
    for (i = start; i < n; i++) {
        swap(&nums[start], &nums[i]);
        permute_swap(nums, start + 1, n, count);
        swap(&nums[start], &nums[i]);
    }
}

int main(void) {
    int nums[] = {1, 2, 3}, count = 0;
    permute_swap(nums, 0, 3, &count);
    printf("%d\n", count); /* 6 */
    return 0;
}

Output & Trace

All permutations for nums = [1, 2, 3]

Partial trace — used + path for [1, 2, 3]

Permutation counts

LeetCode 46 & 47

Optimizations

• Swap in-place: Avoids copying path; good for memory in C/C++.
• next_permutation (C++): Iterative O(n!) generation after sorting once.
• Bitmask used set: Compact used as an integer bitmask for small n.
• Early stop: If only one permutation needed, stop at first base case.

Approach Comparison

Real-Life Applications

Interview Tips

1. State the count upfront: n distinct → n! permutations.
2. Write the used[] template — interviewers recognize it instantly.
3. At base case, append path.copy() / new ArrayList<>(path), not the live path.
4. Mention swap variant if asked for in-place or C-style solution.
5. For duplicates, mention sort + skip-same-at-level rule (LC 47).
6. Contrast with combinations — permutations care about order; combinations do not.