Permutations - Swap Trick

Medium Recursion & Backtracking Permutations

Permutations - Swap Trick is a medium recursion & backtracking problem solved with the permutations pattern. The best approach, swap trick (in place), runs in O(n · n!) time and O(n) space. Below are 2 approaches in Java, from used-array backtracking (for comparison) up.

Problem

Generate every permutation of an array in place by swapping, without a separate used array or path list. It is the same result as Permutations; the goal here is to learn the swap technique.

Examples

Example 1

Input: nums = [1, 2, 3]
Output: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,2,1] [3,1,2]
Why: The order comes from swapping each candidate into position 0, then position 1.

Example 2

Input: nums = [5, 6]
Output: [5,6] [6,5]

Constraints

1 <= nums.length <= 8

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Used-array backtracking (for comparison)	`O(n · n!)`	`O(n)`
Swap trick (in place)	`O(n · n!)`	`O(n)`

1Used-array backtracking (for comparison)

TimeO(n · n!)

SpaceO(n)

Build a separate path, marking elements as used. Correct, but it needs a path list and a boolean array.

For each unused index: mark, add, recurse, unmark, remove.

Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        go(nums, new boolean[nums.length], new ArrayList<>(), out);
        return out;
    }

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

2Swap trick (in place)

TimeO(n · n!)

SpaceO(n)Recursion depth only.

Permute the array itself. At depth i, swap each index j >= i into position i, recurse on i + 1, then swap back. The prefix nums[0..i-1] is the current partial permutation, so no path list or used array is needed.

If i == n, record a copy of nums.
For j from i to n - 1: swap(i, j); recurse(i + 1); swap(i, j).

Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        go(nums, 0, out);
        return out;
    }

    private void go(int[] nums, int i, List<List<Integer>> out) {
        if (i == nums.length) {
            List<Integer> p = new ArrayList<>();
            for (int x : nums) p.add(x);
            out.add(p);
            return;
        }
        for (int j = i; j < nums.length; j++) {
            swap(nums, i, j);
            go(nums, i + 1, out);
            swap(nums, i, j);
        }
    }

    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Edge cases to test

One element
Forgetting to swap back

Hints

Hint 1

Positions 0..i-1 are fixed. Try every element from i..n-1 in position i by swapping it there.

FAQ

What is the best time complexity for Permutations - Swap Trick?

Swap trick (in place) runs in O(n · n!) time and O(n) extra space.

Which pattern does Permutations - Swap Trick use?

It is a recursion & backtracking problem that uses the permutations pattern. Other problems with the same pattern: Permutations, Permutations II.

Is there a brute force solution for Permutations - Swap Trick?

Yes. Used-array backtracking (for comparison) takes O(n · n!) time and O(n) space. Build a separate path, marking elements as used.

Which edge cases should I test for Permutations - Swap Trick?

One element; Forgetting to swap back.