Permutations

Problem Description

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

Examples

Constraints

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

Position by Position, Not Index by Index

Subsets pick a subset of elements starting from a given index. Permutations are different: every element appears in every permutation, just in a different order. That means you can’t iterate forward like in Subsets. You need to choose one unused element for each position.

The cleanest implementation: track which elements you’ve used with a boolean array, and at each recursion level, try every unused element. When the current arrangement reaches length n, you have a complete permutation.

Solution 1: Backtracking with Used Array

import java.util.*;

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

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

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // already in current permutation
            used[i] = true;
            current.add(nums[i]);
            backtrack(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        used = [False] * len(nums)

        def backtrack(current: list[int]):
            if len(current) == len(nums):
                result.append(current[:])
                return

            for i in range(len(nums)):
                if used[i]:
                    continue  # already in current permutation
                used[i] = True
                current.append(nums[i])
                backtrack(current)
                current.pop()
                used[i] = False

        backtrack([])
        return result

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<bool> used(nums.size(), false);
        std::vector<int> current;
        backtrack(nums, used, current, result);
        return result;
    }

private:
    void backtrack(std::vector<int>& nums, std::vector<bool>& used,
                   std::vector<int>& current,
                   std::vector<std::vector<int>>& result) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }

        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push_back(nums[i]);
            backtrack(nums, used, current, result);
            current.pop_back();
            used[i] = false;
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n * n!). There are n! permutations and copying each takes O(n).
• Space Complexity: O(n) for the recursion stack and the used array.

Where it breaks: with n = 6, this generates 720 permutations, which is fast. But n! grows brutally: n = 12 is already 479 million. This problem’s constraints cap at n = 6 precisely because the exponential blowup makes anything larger impractical to enumerate.

Solution 2: Swap-Based (In-Place)

Avoid the used array by swapping elements in place. At each level, the current element is nums[start]; swap it with every position from start to end, recurse, then swap back.

import java.util.*;

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

    private void backtrack(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int n : nums) perm.add(n);
            result.add(perm);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1, result);
            swap(nums, start, i); // restore for next iteration
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }
}

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []

        def backtrack(start: int):
            if start == len(nums):
                result.append(nums[:])
                return

            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # restore

        backtrack(0)
        return result

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }

private:
    void backtrack(std::vector<int>& nums, int start,
                   std::vector<std::vector<int>>& result) {
        if (start == (int)nums.size()) {
            result.push_back(nums);
            return;
        }

        for (int i = start; i < (int)nums.size(); i++) {
            std::swap(nums[start], nums[i]);
            backtrack(nums, start + 1, result);
            std::swap(nums[start], nums[i]); // restore
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n * n!). Same as above.
• Space Complexity: O(n) recursion stack, no used array needed.

Where it breaks: the swap approach modifies the input array during execution. If the input array needs to stay unchanged for other uses, prefer the used array approach.

Common Mistakes

• Forgetting to restore used[i] = false after recursion. Without backtracking, all subsequent iterations see that element as unavailable.
• Collecting results only when current.size() == n - 1. You need the leaf condition to be == n, not == n - 1. Off-by-one here gives you n - 1-length results.
• Not copying the list before adding it to results. Adding the reference means all results will reflect the final backtracked state (empty or partially filled).

Frequently Asked Questions

What is the time complexity of generating all permutations? O(n * n!). The n! accounts for all permutations, and the n factor covers copying each one.

How does this change for Permutations II where elements can repeat? Sort first. In the backtracking loop, skip nums[i] if it equals nums[i-1] and nums[i-1] isn’t currently used. This eliminates duplicate permutations at the source.

What does this test in an interview? Comfort with backtracking state management: tracking what’s been used, undoing choices cleanly, and knowing when a leaf has been reached.

← All Problems