Permutations

Mediumbacktrackingrecursion
Category: Backtracking
Companies that ask this question:
AmazonFacebookGoogleMicrosoftLinkedIn
LeetCode →NeetCode →

Approach

Permutations

Problem Statement

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

Examples

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]]

Intuition

A permutation uses ALL elements in different orders.

For [1,2,3]:

  • First position: 3 choices (1, 2, or 3)
  • Second position: 2 choices (remaining)
  • Third position: 1 choice (last remaining)
  • Total: 3! = 6 permutations

Key: Track which elements are used to avoid duplicates in same permutation.

Pattern Recognition

This is a Backtracking with Used Set problem:

  • Explore all orderings
  • Track used elements
  • Full permutation when length equals n

Approach

Backtracking with Used Set

def backtrack(current):
  if len(current) == len(nums):
    result.append(current.copy())
    return

  for num in nums:
    if num not in current:  # Skip if already used
      current.append(num)
      backtrack(current)
      current.pop()

Alternative: Use boolean array for O(1) lookup instead of set check.

Swap-based Approach

def backtrack(start):
  if start == len(nums):
    result.append(nums.copy())
    return

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

Advantage: No extra space for tracking used elements.

Edge Cases

  • Single element → one permutation
  • Two elements → two permutations
  • Empty array
  • All same value (if duplicates allowed)

Complexity Analysis

  • Time: O(n × n!)

    • n! permutations
    • O(n) to copy each permutation

  • Space: O(n) recursion depth

    • Not counting output (n! permutations)
    • Used set: O(n)

Solution

java
1import java.util.*;
2
3class Solution {
4    public List<List<Integer>> permute(int[] nums) {
5        List<List<Integer>> result = new ArrayList<>();
6        backtrack(new ArrayList<>(), nums, result);
7        return result;
8    }
9
10    private void backtrack(List<Integer> current, int[] nums, List<List<Integer>> result) {
11        // Complete permutation found
12        if (current.size() == nums.length) {
13            result.add(new ArrayList<>(current));
14            return;
15        }
16
17        // Try each number
18        for (int num : nums) {
19            if (current.contains(num)) {  // Skip if already used
20                continue;
21            }
22            current.add(num);
23            backtrack(current, nums, result);
24            current.remove(current.size() - 1);
25        }
26    }
27}
28
Loading visualizer...