Free lesson · DSA Mastery - Interview Prep, End to End

Permutations

Medium7 min readdsarecursion-backtracking

Permutations

Permutations changes the question from which elements to choose to in what order to arrange them. Generate all orderings of a list of distinct numbers. The structural shift from the combination problems is significant: permutations care about position, so instead of a start index that only moves forward (which deliberately ignores order), you track which elements are used and may pick any unused element at each step - producing n! orderings instead of 2^n subsets. This is the canonical "track used elements" backtracking pattern, and it's the foundation for the two permutation variants that follow. We present two equivalent approaches: a used[] boolean array, and an in-place swapping method.

The insight: a permutation uses every element exactly once, in some order. At each position you choose any element not yet placed. Where combinations forbid going backward (to ignore order), permutations allow picking any unused element (because order is exactly what matters) - so the mechanism is a used marker, not a start index.

The Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

Input:  nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input:  nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Approaches Overview

Both generate all n! permutations (each of length n to copy, hence n · n!). The used[] version makes the "pick any unused element" idea explicit; the swapping version fixes one position at a time by swapping candidates into place, using no auxiliary array.

Approach 1: Backtracking with used[] Array - Clearest

The Idea

Maintain a used[] boolean array and a path. Success: when path.size() == n, record. Otherwise loop over all indices i; skip if used[i]; otherwise mark used[i] = true, add nums[i], recurse, then undo both. Because every index is considered at every position (not just those after a start), all n! orderings are produced.

Logic Flowchart

graph TD
    A["backtrack(path, used)"] --> B{"path.size() == n?"}
    B -->|Yes| C["record copy of path; return"]
    B -->|No| D["for i = 0 .. n-1"]
    D --> E{"used[i]?"}
    E -->|Yes| F["skip"]
    E -->|No| G["used[i]=true; path.add(nums[i])"]
    G --> H["backtrack(path, used)"]
    H --> I["path.remove(last); used[i]=false - undo"]
    F --> D
    I --> D

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows permutations with a used array. When the path is full we record it. Otherwise we consider every index, skip those already used, and for each unused index mark it used, add its value, recurse, then unmark and remove to undo. Considering all indices each step yields every ordering.

Code

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;
}

private static void backtrack(int[] nums, boolean[] used,
                              List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));    // full ordering
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                 // already placed
        used[i] = true;                        // choose nums[i] for this position
        path.add(nums[i]);
        backtrack(nums, used, path, result);
        path.remove(path.size() - 1);          // undo value
        used[i] = false;                       // undo used marker
    }
}

// Usage:
// permute([1,2,3]) -> all 6 orderings

This Java code uses a boolean used array. When the path holds all elements it records the permutation. Otherwise it tries every unused index, marks it used, adds its value, recurses, then unmarks and removes to restore state.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [1,2,3]:

graph LR
    F0["pos0 pick 1; pos1 pick 2; pos2 pick 3 → [1,2,3]"]
    F1["undo: pos1 pick 3; pos2 pick 2 → [1,3,2]"]
    F2["undo to pos0: pick 2 → [2,1,3],[2,3,1]"]
    F3["pick 3 → [3,1,2],[3,2,1]"]
    F4["6 permutations"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough permutes one, two, three. Fixing the first element as one yields one-two-three and one-three-two; as two yields two-one-three and two-three-one; as three yields three-one-two and three-two-one - six orderings in all.

Result: all 6 permutations of [1,2,3].

Complexity

Time: O(n · n!) - n! permutations, each O(n) to copy. Space: O(n) recursion depth + O(n) used.

Approach 2: Backtracking with In-Place Swaps - No Extra Array

The Idea

Fix positions left to right. At position start, swap each candidate index i (from start to n-1) into start, recurse on start + 1, then swap back (undo). The prefix [0, start) holds the fixed elements; the suffix is the pool of remaining candidates. No used array is needed - the swap itself tracks placement, and the array is the working state.

Logic Flowchart

graph TD
    A["permute(start)"] --> B{"start == n?"}
    B -->|Yes| C["record copy of nums; return"]
    B -->|No| D["for i = start .. n-1"]
    D --> E["swap(start, i)"]
    E --> F["permute(start + 1)"]
    F --> G["swap(start, i) - undo"]
    G --> H{"more i?"}
    H -->|Yes| D
    H -->|No| I["return"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the in-place swap method. To fill a position, each candidate from that position onward is swapped into place, the next position is filled recursively, then the swap is undone. When all positions are fixed, the array is recorded.

Code

public static List<List<Integer>> permuteSwap(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    permuteFrom(nums, 0, result);
    return result;
}

private static void permuteFrom(int[] nums, int start, List<List<Integer>> result) {
    if (start == nums.length) {
        List<Integer> perm = new ArrayList<>();
        for (int v : nums) perm.add(v);        // snapshot current arrangement
        result.add(perm);
        return;
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);                  // place nums[i] at position `start`
        permuteFrom(nums, start + 1, result);
        swap(nums, start, i);                  // undo
    }
}

private static void swap(int[] a, int x, int y) { int t = a[x]; a[x] = a[y]; a[y] = t; }

This Java code permutes by swapping. For each position it swaps every later candidate into place, recurses to fill the next position, then swaps back. When every position is fixed it snapshots the array as one permutation.

Complexity

Time: O(n · n!). Space: O(n) recursion depth, no auxiliary used array.

Complexity Comparison

Both are optimal (output is n!). The used[] version is the better teaching and interview default because it reads directly as "pick any unused element" and extends cleanly to the duplicate variant. The swap version is slick and memory-light but trickier to adapt for duplicate handling.

Variations & Follow-ups

Why a used[] array here instead of a start index?

A start index enforces increasing order, which is exactly how combinations ignore order - perfect when order doesn't matter. Permutations need every ordering, so you must be able to pick elements in any sequence, including "earlier" ones. The used[] array lets you choose any not-yet-placed element at each position, generating all n! arrangements.

Why n! permutations versus 2^n subsets?

A subset is n independent include/exclude decisions → 2^n. A permutation fills n positions: n choices for the first, n-1 for the second, and so on → n!. The combinatorics differ because permutations use all elements and care about order, while subsets choose a subset and ignore order.

How does the swap method avoid a used array?

The array is partitioned into a fixed prefix [0, start) and a candidate suffix [start, n). Swapping a suffix element into start "places" it; the recursion then permutes the smaller suffix. Swapping back restores the pool. Placement is encoded in the array layout itself, so no separate marker is needed.

Which is better for the duplicate variant (Permutations II)?

The used[] version, by a wide margin. Handling duplicates requires sorting and a sibling-skip condition (i > 0 && nums[i] == nums[i-1] && !used[i-1]) that's clean with explicit used markers but awkward with swaps (swapping disturbs the sorted order the skip relies on). That's why the next problem builds on the used[] form.

What about edge cases?

• Single element (Example 3): One permutation, [1].
• Two elements (Example 2): Two permutations.
• All distinct (guaranteed): No duplicate handling needed here.
• Maximum n = 6: 6! = 720 permutations - small and fast.

Common Interview Pitfalls

• Using a start index. That generates combinations/subsets, not permutations - a frequent conceptual slip.
• Forgetting to reset used[i] = false. Sibling positions then can't reuse the element, dropping valid permutations.
• Swapping but forgetting to swap back. Corrupts the array for sibling branches.
• Recording by reference. Snapshot the path/array; the shared structure mutates afterward.

Why This Topic Matters

Permutations introduces the "track used elements" backtracking pattern - the counterpart to the combination family's start-index pattern. Knowing when order matters (use used[], consider all elements) versus when it doesn't (use start, go forward only) is one of the most important distinctions in backtracking, and it determines the entire structure of the search.

The next topic, Letter Combinations of a Phone Number, applies permutation-style "pick one per position" backtracking to a mapping problem: each digit maps to a set of letters, and you generate every combination of letters across the digits. It's a different flavor - the choices at each position come from a digit-to-letters table rather than a shared pool - but the choose-one-per-position-and-recurse structure is the same skeleton you just built.

Back to DSA Mastery - Interview Prep, End to End