Permutations

MediumSubsets (BFS-style generation)NeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array nums of distinct integers. Return every permutation, meaning every possible ordering that uses each element exactly once, n! of them for n numbers. Order matters here, so [1,2,3] and [3,2,1] are different permutations and both appear. The permutations can be returned in any order.

Examples

nums = [1,2,3] returns [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Any of the 3 numbers can go first, either of the remaining 2 can go second, and the last one is forced, giving 3 * 2 * 1 = 6 orderings.

nums = [0,1] returns [[0,1],[1,0]]

Two numbers can be arranged in 2 ways: 0 before 1, or 1 before 0.

Constraints

1 <= nums.length <= 6
All numbers distinct.

Hints

Hint 1

Each permutation is a sequence of decisions: which unused element comes next?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Fill positions one at a time. Keep a path of chosen numbers and a used[] flag per index; at each step try every unused number: mark it, append it, recurse, then pop it and unmark it so the next choice starts from the same state. When the path holds all n numbers, save a copy. O(n * n!) time, since each of the n! permutations is copied in O(n), and O(n) extra space besides the output.

Time

O(n * n!)

Space

O(n)

Pitfall

Saving path itself instead of a copy. Every saved entry then points to the same list, which is empty once the recursion finishes. Undo both the append and the used flag after each recursive call.

Solutions

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

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, 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, path, used, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

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

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

        backtrack([])
        return result