Permutations solution and explanation
Infosys
Google
9 more videos on this problem
Backtracking: Permutations - Leetcode 46 - PythonNeetCode · 9:43 · 422K views
Permutations - Leetcode 46 - PythonNeetCodeIO · 11:58 · 132K views
Leetcode 46. Permutations : Introduction to backtrackingComputerBread · 10:06 · 128K views
Permutations (LeetCode 46) | Full solution with backtracking examples | Interview | Study AlgorithmsNikhil Lohia · 16:55 · 120K views
Permutations | INTUITIVE | Backtracking Template | Two Ways | Similar Problems | Leetcode 46codestorywithMIK · 36:36 · 49K views
Permutations - Leetcode 46 - Recursive Backtracking (Python)Greg Hogg · 9:42 · 41K views
Permutations | Live Coding with Explanation | Leetcode #46Algorithms Made Easy · 5:45 · 23K views
LEETCODE 46 (JAVASCRIPT) | PERMUTATIONS IAndy Gala · 14:49 · 14K views
Permutations leetcode java - Leetcode 46 PermutationsJK Codes · 7:31 · 2K views
Permutations - 46. LeetCode - JavaTeddy Smith · 8:54 · 1K views
The problem
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
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]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
Approach overview
Problem Overview: Given an array of distinct integers, return all possible permutations of the numbers. Each permutation represents a different ordering of the same elements, and the result must include every possible arrangement.
Approach 1: Backtracking (Time: O(n! * n), Space: O(n))
This problem naturally fits backtracking. You build permutations incrementally by choosing an unused element, adding it to the current path, and recursively exploring further choices. A boolean used[] array or in-place swapping ensures each element appears only once in the current permutation.
The key insight is that every position in the permutation can be filled by any unused element. For each recursive level, iterate through the array, pick an unused number, append it to the current permutation, and recurse. Once the permutation length reaches n, add a copy to the result list. Then backtrack by removing the last element and marking it unused.
This generates exactly n! permutations. Copying each permutation takes O(n), which leads to an overall time complexity of O(n! * n). The recursion depth is O(n), and auxiliary space is mainly the recursion stack and the current permutation. Backtracking is the most common interview solution and heavily relies on concepts from recursion and array traversal.
Approach 2: Iterative Permutation Generation (Time: O(n! * n), Space: O(n!))
An iterative strategy builds permutations progressively. Start with a list containing an empty permutation. For each number in the input array, insert it into every possible position of every existing permutation. If a permutation has length k, inserting the new number produces k + 1 new permutations.
Example: starting with [ ], inserting 1 gives [1]. Inserting 2 into [1] creates [2,1] and [1,2]. Continue inserting the next element into every position of each existing permutation until all numbers are processed.
This approach avoids recursion and can be easier to reason about in iterative environments. However, it repeatedly copies arrays when inserting elements, which increases memory overhead. The total number of generated permutations is still n!, and each insertion operation costs up to O(n), resulting in O(n! * n) time complexity.
Recommended for interviews: Backtracking is the expected approach. It demonstrates control over recursion, state management, and pruning. Interviewers usually want to see the recursive exploration pattern and proper backtracking logic. The iterative insertion approach is useful as an alternative but appears less frequently in coding interviews.
Approach 1: Backtracking Approach
This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.
def permute(nums):
def backtrack(first=0):
if first == n:
output.append(nums[:])
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
backtrack()
return output
print(permute([1, 2, 3]))import java.util.ArrayList;
import java.util.List;
public class Permutations {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, result, new ArrayList<Integer>(), new boolean[nums.length]);
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> tempList, boolean[] used) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
tempList.add(nums[i]);
backtrack(nums, result, tempList, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}
public static void main(String[] args) {
Permutations permutations = new Permutations();
int[] nums = {1, 2, 3};
System.out.println(permutations.permute(nums));
}
}#include <vector>
#include <algorithm>
#include <iostream>
std::vector<std::vector<int>> permute(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::sort(nums.begin(), nums.end());
do {
result.push_back(nums);
} while (std::next_permutation(nums.begin(), nums.end()));
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::vector<std::vector<int>> result = permute(nums);
for (const auto& permutation : result) {
for (int num : permutation) {
std::cout << num << " ";
}
std::cout << "\n";
}
return 0;
}function permute(nums) {
const result = [];
const backtrack = (path) => {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (const num of nums) {
if (!path.includes(num)) {
path.push(num);
backtrack(path);
path.pop();
}
}
};
backtrack([]);
return result;
}
console.log(permute([1, 2, 3]));#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize, int* returnColumnSizes) {
if (start == numsSize) {
result[*returnSize] = (int*)malloc(sizeof(int) * numsSize);
for (int i = 0; i < numsSize; i++) {
result[*returnSize][i] = nums[i];
}
returnColumnSizes[*returnSize] = numsSize;
(*returnSize)++;
} else {
for (int i = start; i < numsSize; i++) {
swap(&nums[start], &nums[i]);
backtrack(nums, numsSize, start + 1, result, returnSize, returnColumnSizes);
swap(&nums[start], &nums[i]);
}
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int factorial = 1;
for (int i = 2; i <= numsSize; i++) {
factorial *= i;
}
int** result = (int**)malloc(sizeof(int*) * factorial);
*returnColumnSizes = (int*)malloc(sizeof(int) * factorial);
*returnSize = 0;
backtrack(nums, numsSize, 0, result, returnSize, *returnColumnSizes);
return result;
}
int main() {
int nums[] = {1, 2, 3};
int returnSize;
int* returnColumnSizes;
int** result = permute(nums, 3, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
for (int i = 0; i < returnSize; i++) {
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class Permutations {
public IList<IList<int>> Permute(int[] nums) {
var result = new List<IList<int>>();
Backtrack(nums, new List<int>(), result);
return result;
}
private void Backtrack(int[] nums, List<int> tempList, List<IList<int>> result) {
if (tempList.Count == nums.Length) {
result.Add(new List<int>(tempList));
} else {
for (int i = 0; i < nums.Length; i++) {
if (tempList.Contains(nums[i])) continue;
tempList.Add(nums[i]);
Backtrack(nums, tempList, result);
tempList.RemoveAt(tempList.Count - 1);
}
}
}
public static void Main(string[] args) {
var permutations = new Permutations();
int[] nums = {1, 2, 3};
var result = permutations.Permute(nums);
foreach (var perm in result) {
Console.WriteLine(string.Join(", ", perm));
}
}
}This Python implementation uses a recursive backtracking approach to generate the permutations. It swaps the elements to fix elements at each recursive level and then backtracks to get back to the previous state.
Time Complexity: O(n * n!) as all permutations are generated and stored.
Space Complexity: O(n!) is required to store all permutations, and O(n) for recursion call stack.
Approach 2: Iterative Permutation Generation
An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.
from itertools import permutations
def permute(nums):
return list(permutations(nums))
print(permute([1, 2, 3]))import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
public class Permutations {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
Arrays.sort(nums);
do {
List<Integer> current = new ArrayList<>();
for (int num : nums) {
current.add(num);
}
results.add(new ArrayList<>(current));
} while (nextPermutation(nums));
return results;
}
private boolean nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i < 0) return false;
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--;
swap(nums, i, j);
reverse(nums, i + 1);
return true;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) swap(nums, i++, j--);
}
public static void main(String[] args) {
Permutations perm = new Permutations();
int[] nums = {1, 2, 3};
List<List<Integer>> results = perm.permute(nums);
System.out.println(results);
}
}#include <vector>
#include <iostream>
#include <algorithm>
std::vector<std::vector<int>> permute(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::sort(nums.begin(), nums.end());
do {
result.push_back(nums);
} while (std::next_permutation(nums.begin(), nums.end()));
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::vector<std::vector<int>> result = permute(nums);
for (const auto& perm : result) {
for (int num : perm) {
std::cout << num << " ";
}
std::cout << '\n';
}
return 0;
}function permute(nums) {
const res = [];
const nextPermutation = (arr) => {
let i = arr.length - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) i--;
if (i < 0) return false;
let j = arr.length - 1;
while (arr[j] <= arr[i]) j--;
[arr[i], arr[j]] = [arr[j], arr[i]];
arr = arr.slice(0, i + 1).concat(arr.slice(i + 1).reverse());
return arr;
};
nums.sort((a, b) => a - b);
res.push([...nums]);
while (nums = nextPermutation(nums.slice())) {
res.push([...nums]);
}
return res;
}
console.log(permute([1, 2, 3]));#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int factorial = 1;
for (int i = 2; i <= numsSize; i++) {
factorial *= i;
}
int** result = (int**)malloc(sizeof(int*) * factorial);
*returnColumnSizes = (int*)malloc(sizeof(int) * factorial);
*returnSize = 0;
int* current = (int*)malloc(sizeof(int) * numsSize);
for (int i = 0; i < numsSize; i++) {
current[i] = nums[i];
}
for (int i = 0; i < factorial; i++) {
result[i] = (int*)malloc(sizeof(int) * numsSize);
for (int j = 0; j < numsSize; j++) {
result[i][j] = current[j];
}
(*returnColumnSizes)[i] = numsSize;
int j = numsSize - 1;
while (j > 0 && current[j - 1] >= current[j]) {
j--;
}
if (j > 0) {
int swapIndex = numsSize - 1;
while (current[swapIndex] <= current[j - 1]) {
swapIndex--;
}
swap(¤t[j - 1], ¤t[swapIndex]);
}
for (int k = j, l = numsSize - 1; k < l; k++, l--) {
swap(¤t[k], ¤t[l]);
}
}
free(current);
return result;
}
int main() {
int nums[] = {1, 2, 3};
int returnSize;
int* returnColumnSizes;
int** result = permute(nums, 3, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
for (int i = 0; i < returnSize; i++) {
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class Permutations {
public IList<IList<int>> Permute(int[] nums) {
List<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
do {
result.Add(new List<int>(nums));
} while (NextPermutation(nums));
return result;
}
private bool NextPermutation(int[] nums) {
int i = nums.Length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i < 0) return false;
int j = nums.Length - 1;
while (nums[j] <= nums[i]) j--;
Swap(nums, i, j);
Array.Reverse(nums, i + 1, nums.Length - i - 1);
return true;
}
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) {
var permutations = new Permutations();
int[] nums = {1, 2, 3};
var result = permutations.Permute(nums);
foreach (var perm in result) {
Console.WriteLine(string.Join(", ", perm));
}
}
}This Python solution uses the itertools.permutations function that directly generates permutations using combinatorial generation, simplifying implementation.
Time Complexity: O(n * n!) inherently due to combination generation.
Space Complexity: O(n!) for storing final permutations.
Approach 3: DFS (Backtracking)
We design a function dfs(i) to represent that the first i positions have been filled, and now we need to fill the i+1 position. We enumerate all possible numbers, if this number has not been filled, we fill in this number, and then continue to fill the next position, until all positions are filled.
The time complexity is O(n times n!), where n is the length of the array. There are n! permutations in total, and each permutation takes O(n) time to construct.
Similar problems:
function permute(nums: number[]): number[][] {
const n = nums.length;
const ans: number[][] = [];
const vis: boolean[] = Array(n).fill(false);
const t: number[] = Array(n).fill(0);
const dfs = (i: number) => {
if (i >= n) {
ans.push(t.slice());
return;
}
for (let j = 0; j < n; ++j) {
if (!vis[j]) {
vis[j] = true;
t[i] = nums[j];
dfs(i + 1);
vis[j] = false;
}
}
};
dfs(0);
return ans;
}func permute(nums []int) (ans [][]int) {
n := len(nums)
t := make([]int, n)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, slices.Clone(t))
return
}
for j, x := range nums {
if !vis[j] {
vis[j] = true
t[i] = x
dfs(i + 1)
vis[j] = false
}
}
}
dfs(0)
return
}impl Solution {
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
let n = nums.len();
let mut ans = Vec::new();
let mut t = vec![0; n];
let mut vis = vec![false; n];
fn dfs(
nums: &Vec<i32>,
n: usize,
t: &mut Vec<i32>,
vis: &mut Vec<bool>,
ans: &mut Vec<Vec<i32>>,
i: usize
) {
if i == n {
ans.push(t.clone());
return;
}
for j in 0..n {
if !vis[j] {
vis[j] = true;
t[i] = nums[j];
dfs(nums, n, t, vis, ans, i + 1);
vis[j] = false;
}
}
}
dfs(&nums, n, &mut t, &mut vis, &mut ans, 0);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(n * n!) as all permutations are generated and stored. |
| Iterative Permutation Generation | Time Complexity: O(n * n!) inherently due to combination generation. |
| DFS (Backtracking) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(n! * n) | O(n) | Standard interview approach for generating permutations using recursion |
| Iterative Permutation Generation | O(n! * n) | O(n!) | When recursion is avoided or when building permutations iteratively |
Frequently asked questions
Is Permutations easy or hard?
Permutations is considered a medium difficulty problem. The implementation requires understanding recursion and backtracking, but the core idea is straightforward once you visualize choosing elements and undoing choices after each recursive call.
Permutations Python/Java solution
Python and Java solutions typically implement recursive backtracking. A list stores the current permutation, a boolean array tracks used numbers, and when the permutation length reaches n it gets copied into the result list.
How to solve Permutations in O(n)?
Generating every permutation cannot be done in O(n) because the output itself contains n! permutations. The optimal approach is O(n! * n) using backtracking or iterative insertion. The factorial growth comes from the number of possible arrangements.
What is the best approach for Permutations?
Backtracking is the most common and interview-preferred approach. It builds permutations step by step, recursively selecting unused elements and backtracking after exploring each branch. This guarantees all n! permutations are generated with O(n! * n) time complexity.
Is Permutations asked at Google/Amazon/Meta?
Permutation generation problems frequently appear in interviews at companies like Amazon, Google, and Meta. They test recursion, backtracking, and the ability to explore combinatorial search spaces efficiently.
What data structure is used in Permutations?
Most solutions use arrays or lists to store the current permutation and a boolean array or set to track used elements. Recursive backtracking relies on the call stack to explore choices and revert state after each branch.
What is the time complexity of Permutations?
Generating all permutations requires O(n! * n) time. There are n! possible permutations of n elements, and copying each permutation into the result list costs O(n). Any algorithm that lists all permutations will have at least factorial complexity.