Permutations

Problem Statement

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

A permutation is an arrangement of all elements where order matters: [1,2] and [2,1] are different permutations.

What to notice first

• The total number of permutations is n! (factorial).
• For an array of length n, each element can be placed in the first position, leaving n-1 elements for the remaining positions.
• You must generate all possible orderings without repetition.

Examples

Input	Output	Explanation
[1,2,3]	[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]	6 unique orderings (3! = 6)
[0,1]	[[0,1], [1,0]]	2 unique orderings (2! = 2)
[1]	[[1]]	1 unique ordering (1! = 1)

Constraints

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

Real-World Applications

Where this pattern appears

• Scheduling problems — finding all possible orderings of tasks to analyze different schedules.
• Route optimization — generating all possible routes to visit a set of locations (traveling salesman problem).
• Genetic algorithms — exploring different gene arrangements as candidate solutions.
• Game AI — evaluating all possible move sequences in chess or other games.

Complexity Comparison

Approach	Time	Space	Memory	Best When
Swap (In-place)	O(n! * n)	O(n!)	O(1) extra	Want minimal extra memory, cleaner code
Used Array	O(n! * n)	O(n!)	O(n) extra	Prefer keeping original array unmodified

Which approach should you learn first?

• Pick Swap if you want an elegant, space-efficient solution.
• Pick Used Array if you prefer a more explicit choice-explore-unchoose pattern.

Most Elegant

Swap

O(n! * n) time · O(n!) space

Most Explicit

Used Array

O(n! * n) time · O(n!) space

Approach 1: Backtracking with Swap (Recommended)

★ Recommended

Build permutations by treating the array as having a “fixed” portion and a “to-be-determined” portion. For each position first, try each remaining element in that position. Swap it in, recursively solve for the rest, then swap it back.

This is elegant because it requires no extra tracking data structure—the array itself tracks which elements are available.

⏱ Time O(n! * n) n! perms, n work per perm 💾 Space O(n!) Result storage

Step-by-step Example

Input: nums = [1, 2, 3]

first	current	action
0	[1, 2, 3]	Fix 1 at position 0, recurse on [2,3]
1	[1, 2, 3]	Fix 2 at position 1, recurse on [3]
2	[1, 2, 3]	Base case: save [1,2,3] ✓
1	[1, 3, 2]	Swap 2 and 3, save [1,3,2] ✓
0	[2, 1, 3]	Swap 1 and 2, fix 2 at position 0
1	[2, 1, 3]	Explore rest; save [2,1,3] ✓

Pseudocode

function permutationsSwap(nums):
    result = []

    function backtrack(first):
        if first == len(nums):
            result.append(copy of nums)
            return

        for i from first to len(nums)-1:
            swap(nums[first], nums[i])
            backtrack(first + 1)
            swap(nums[first], nums[i])  # Backtrack

    backtrack(0)
    return result

Solution Code

Python

permutations_swap.py

from typing import List


def permutations_swap(nums: List[int]) -> List[List[int]]:
    """
    Generate all permutations using backtracking with swapping approach.
    Time: O(n! * n), Space: O(n!) for result
    """
    result = []

    def backtrack(first: int) -> None:
        # Base case: all elements are placed
        if first == len(nums):
            result.append(nums[:])  # Make a copy
            return

        for i in range(first, len(nums)):
            # Swap
            nums[first], nums[i] = nums[i], nums[first]
            # Backtrack
            backtrack(first + 1)
            # Swap back
            nums[first], nums[i] = nums[i], nums[first]

    backtrack(0)
    return result


print(permutations_swap([1, 2, 3]))
# Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

C++

permutations_swap.cpp

#include <vector>
using namespace std;

class Solution {
public:
    /**
     * Generate all permutations using backtracking with swapping approach.
     * Time: O(n! * n), Space: O(n!) for result
     */
    vector<vector<int>> permute(vector<int> nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int first, vector<vector<int>>& result) {
        // Base case: all elements are placed
        if (first == nums.size()) {
            result.push_back(nums);
            return;
        }

        for (int i = first; i < nums.size(); i++) {
            // Swap
            swap(nums[first], nums[i]);
            // Backtrack
            backtrack(nums, first + 1, result);
            // Swap back
            swap(nums[first], nums[i]);
        }
    }
};

// Test
int main() {
    Solution sol;
    vector<vector<int>> result = sol.permute({1, 2, 3});
    // Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
    return 0;
}

Java

PermutationsSwap.java

import java.util.*;

public class PermutationsSwap {
    /**
     * Generate all permutations using backtracking with swapping approach.
     * Time: O(n! * n), Space: O(n!) for result
     */
    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 first, List<List<Integer>> result) {
        // Base case: all elements are placed
        if (first == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) {
                perm.add(num);
            }
            result.add(perm);
            return;
        }

        for (int i = first; i < nums.length; i++) {
            // Swap
            swap(nums, first, i);
            // Backtrack
            backtrack(nums, first + 1, result);
            // Swap back
            swap(nums, first, i);
        }
    }

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

    public static void main(String[] args) {
        PermutationsSwap sol = new PermutationsSwap();
        System.out.println(sol.permute(new int[]{1, 2, 3}));
        // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    }
}

JavaScript

permutations_swap.js

/**
 * Generate all permutations using backtracking with swapping approach.
 * Time: O(n! * n), Space: O(n!) for result
 * @param {number[]} nums
 * @return {number[][]}
 */
function permutationsSwap(nums) {
    const result = [];

    function backtrack(first) {
        // Base case: all elements are placed
        if (first === nums.length) {
            result.push([...nums]);
            return;
        }

        for (let i = first; i < nums.length; i++) {
            // Swap
            [nums[first], nums[i]] = [nums[i], nums[first]];
            // Backtrack
            backtrack(first + 1);
            // Swap back
            [nums[first], nums[i]] = [nums[i], nums[first]];
        }
    }

    backtrack(0);
    return result;
}

console.log(permutationsSwap([1, 2, 3]));
// Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Rust

permutations_swap.rs

pub fn permutations_swap(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut nums = nums;
    backtrack(&mut nums, 0, &mut result);
    result
}

fn backtrack(nums: &mut Vec<i32>, first: usize, result: &mut Vec<Vec<i32>>) {
    // Base case: all elements are placed
    if first == nums.len() {
        result.push(nums.clone());
        return;
    }

    for i in first..nums.len() {
        // Swap
        nums.swap(first, i);
        // Backtrack
        backtrack(nums, first + 1, result);
        // Swap back
        nums.swap(first, i);
    }
}

fn main() {
    let result = permutations_swap(vec![1, 2, 3]);
    println!("{:?}", result);
    // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}

Go

permutations_swap.go

package main

import "fmt"

func permutationsSwap(nums []int) [][]int {
  var result [][]int
  backtrack(nums, 0, &result)
  return result
}

func backtrack(nums []int, first int, result *[][]int) {
  // Base case: all elements are placed
  if first == len(nums) {
    perm := make([]int, len(nums))
    copy(perm, nums)
    *result = append(*result, perm)
    return
  }

  for i := first; i < len(nums); i++ {
    // Swap
    nums[first], nums[i] = nums[i], nums[first]
    // Backtrack
    backtrack(nums, first+1, result)
    // Swap back
    nums[first], nums[i] = nums[i], nums[first]
  }
}

func main() {
  fmt.Println(permutationsSwap([]int{1, 2, 3}))
  // Output: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
}

Approach 2: Backtracking with Used Array

🎯 Interview Favourite

Build permutations by explicitly tracking which elements have been used. Maintain a boolean array marking visited elements. For each position, try each unused element, mark it as used, recurse, then unmark it.

This approach is more explicit about the choice/explore/unchoose pattern and leaves the original array untouched.

⏱ Time O(n! * n) n! perms, n work per perm 💾 Space O(n!) Result storage + used array

Step-by-step Example

Input: nums = [1, 2, 3]

current	used	action
[1]	[T,F,F]	Choose 1, explore [2,3]
[1,2]	[T,T,F]	Choose 2, explore [3]
[1,2,3]	[T,T,T]	Save [1,2,3] ✓
[1,3]	[T,F,T]	Unchoose 2, choose 3
[1,3,2]	[T,T,T]	Save [1,3,2] ✓
[2]	[F,T,F]	Unchoose 1, choose 2

Pseudocode

function permutationsUsedArray(nums):
    result = []
    used = [false] * len(nums)
    current = []

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

        for i from 0 to len(nums)-1:
            if used[i]:
                continue

            current.append(nums[i])
            used[i] = true
            backtrack()
            current.pop()
            used[i] = false

    backtrack()
    return result

Solution Code

Python

permutations_used_array.py

from typing import List


def permutations_used_array(nums: List[int]) -> List[List[int]]:
    """
    Generate all permutations using backtracking with used array.
    Time: O(n! * n), Space: O(n!) for result
    """
    result = []
    used = [False] * len(nums)

    def backtrack(current: List[int]) -> None:
        # Base case: we've used all numbers
        if len(current) == len(nums):
            result.append(current[:])  # Make a copy
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            # Choose
            current.append(nums[i])
            used[i] = True
            # Explore
            backtrack(current)
            # Unchoose
            current.pop()
            used[i] = False

    backtrack([])
    return result


print(permutations_used_array([1, 2, 3]))
# Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

C++

permutations_used_array.cpp

#include <vector>
using namespace std;

class Solution {
public:
    /**
     * Generate all permutations using backtracking with used array.
     * Time: O(n! * n), Space: O(n!) for result
     */
    vector<vector<int>> permute(vector<int> nums) {
        vector<vector<int>> result;
        vector<bool> used(nums.size(), false);
        vector<int> current;
        backtrack(nums, used, current, result);
        return result;
    }

private:
    void backtrack(const vector<int>& nums, vector<bool>& used, vector<int>& current,
                   vector<vector<int>>& result) {
        // Base case: we've used all numbers
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;

            // Choose
            current.push_back(nums[i]);
            used[i] = true;
            // Explore
            backtrack(nums, used, current, result);
            // Unchoose
            current.pop_back();
            used[i] = false;
        }
    }
};

// Test
int main() {
    Solution sol;
    vector<vector<int>> result = sol.permute({1, 2, 3});
    // Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
    return 0;
}

Java

PermutationsUsedArray.java

import java.util.*;

public class PermutationsUsedArray {
    /**
     * Generate all permutations using backtracking with used array.
     * Time: O(n! * n), Space: O(n!) for result
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        List<Integer> current = new ArrayList<>();
        backtrack(nums, used, current, result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> current,
                          List<List<Integer>> result) {
        // Base case: we've used all numbers
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            // Choose
            current.add(nums[i]);
            used[i] = true;
            // Explore
            backtrack(nums, used, current, result);
            // Unchoose
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        PermutationsUsedArray sol = new PermutationsUsedArray();
        System.out.println(sol.permute(new int[]{1, 2, 3}));
        // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    }
}

JavaScript

permutations_used_array.js

/**
 * Generate all permutations using backtracking with used array.
 * Time: O(n! * n), Space: O(n!) for result
 * @param {number[]} nums
 * @return {number[][]}
 */
function permutationsUsedArray(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    const current = [];

    function backtrack() {
        // Base case: we've used all numbers
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            // Choose
            current.push(nums[i]);
            used[i] = true;
            // Explore
            backtrack();
            // Unchoose
            current.pop();
            used[i] = false;
        }
    }

    backtrack();
    return result;
}

console.log(permutationsUsedArray([1, 2, 3]));
// Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Rust

permutations_used_array.rs

pub fn permutations_used_array(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut used = vec![false; nums.len()];
    let mut current = vec![];
    backtrack(&nums, &mut used, &mut current, &mut result);
    result
}

fn backtrack(nums: &Vec<i32>, used: &mut Vec<bool>, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    // Base case: we've used all numbers
    if current.len() == nums.len() {
        result.push(current.clone());
        return;
    }

    for i in 0..nums.len() {
        if used[i] {
            continue;
        }

        // Choose
        current.push(nums[i]);
        used[i] = true;
        // Explore
        backtrack(nums, used, current, result);
        // Unchoose
        current.pop();
        used[i] = false;
    }
}

fn main() {
    let result = permutations_used_array(vec![1, 2, 3]);
    println!("{:?}", result);
    // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}

Go

permutations_used_array.go

package main

import "fmt"

func permutationsUsedArray(nums []int) [][]int {
  var result [][]int
  used := make([]bool, len(nums))
  var current []int

  var backtrack func()
  backtrack = func() {
    // Base case: we've used all numbers
    if len(current) == len(nums) {
      perm := make([]int, len(current))
      copy(perm, current)
      result = append(result, perm)
      return
    }

    for i := 0; i < len(nums); i++ {
      if used[i] {
        continue
      }

      // Choose
      current = append(current, nums[i])
      used[i] = true
      // Explore
      backtrack()
      // Unchoose
      current = current[:len(current)-1]
      used[i] = false
    }
  }

  backtrack()
  return result
}

func main() {
  fmt.Println(permutationsUsedArray([]int{1, 2, 3}))
  // Output: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
}

Common mistakes

Watch for these pitfalls

• Forgetting to save a copy in the swap approach; appending the reference will make all results point to the same array.
• Not swapping back after recursion; the second swap in the swap approach is critical for correctness.
• Using a set or set operations in the used array approach when a boolean array is much faster.
• Modifying the nums array in place without restoring it can cause issues if the array is used elsewhere.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

permutations_space_optimized.py

"""
Solution for Permutations
"""

def solve():
    """Implementation for approach 3 of Permutations"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

permutations_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Permutations
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

PermutationsSpaceOptimized.java

/**
 * Solution for Permutations
 * Approach 3
 */
public class PermutationsSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

permutations_space_optimized.js

/**
 * Solution for Permutations
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

permutations_space_optimized.rs

/// Solution for Permutations
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

permutations_space_optimized.go

package main

import "fmt"

// Solution for Permutations
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Combinations ↗ Medium #77
• Permutations II ↗ Medium #47
• Combination Sum ↗ Medium #39
• Letter Combinations of a Phone Number ↗ Medium #17

Interview Tips

Key trade-offs to discuss

• Swap vs Used Array: Swap is more elegant and uses less extra memory; used array is clearer conceptually. Both are O(n!) time and space.
• Time complexity growth: n! grows extremely fast: 3! = 6, 5! = 120, 7! = 5040. This is why the constraint is n <= 6.
• Space optimization: The result list itself uses O(n! * n) space, which is unavoidable since we must return all permutations.
• Follow-up — Permutations with Duplicates: If the array has duplicates, sort first, then skip duplicate elements during recursion to avoid duplicate permutations.

← Previous
#45 Jump Game II Next
#47 Permutations II →