Permutations
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a classic backtracking algorithm. We build a permutation step-by-step using a recursive helper function. To avoid using the same element multiple times in a single permutation, we maintain a boolean used array.
Algorithm
- Initialize an empty list
resultto store all permutations. - Initialize a boolean array
usedof the same size asnums, with all values set tofalse. - Define a recursive function
backtrack(currentPermutation): a. Base Case: IfcurrentPermutation.size()is equal tonums.length, it means we have formed a complete permutation. Add a copy ofcurrentPermutationtoresultand return. b. Recursive Step: Iterate through each number in thenumsarray from indexi = 0tonums.length - 1. i. If the number at indexihas not been used yet (used[i]isfalse): - Addnums[i]tocurrentPermutation. - Mark it as used by settingused[i]totrue. - Make a recursive call:backtrack(currentPermutation). - Backtrack: After the recursive call returns, undo the choice. Setused[i]back tofalseand remove the last element fromcurrentPermutation. - Start the process by making an initial call to
backtrackwith an empty list. - Return the
resultlist.
Walkthrough
The core of this solution is a recursive function, let's call it backtrack. This function is responsible for building permutations. We pass it the list of results, the current permutation being built, the original numbers, and a used array.
The base case for the recursion is when the size of the current permutation equals the size of the input nums array. This signifies that a complete, valid permutation has been formed. We then add a copy of this permutation to our final result list and return from that recursive call.
In the recursive step, we loop through all the numbers in the input array. For each number, we check our used array to see if it has already been included in the current permutation. If it hasn't, we add it to our current permutation, mark it as used, and then make a recursive call to continue building the permutation from this new state.
Once the recursive call returns, we must "backtrack". This is a critical step where we undo the choice we just made so that we can explore other possibilities. We remove the number we just added from the current permutation and update its status in the used array back to false. This allows that number to be picked at a different position in a future permutation.
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(result, new ArrayList<>(), nums, used); return result; } private void backtrack(List<List<Integer>> result, List<Integer> currentPermutation, int[] nums, boolean[] used) { if (currentPermutation.size() == nums.length) { result.add(new ArrayList<>(currentPermutation)); return; } for (int i = 0; i < nums.length; i++) { if (!used[i]) { currentPermutation.add(nums[i]); used[i] = true; backtrack(result, currentPermutation, nums, used); // Backtrack used[i] = false; currentPermutation.remove(currentPermutation.size() - 1); } } }}Complexity
Time
O(N * N!)
Space
O(N)
Trade-offs
Pros
Conceptually straightforward and a very common pattern for solving permutation, combination, and subset problems.
Easy to understand and implement.
Cons
Requires extra space for the
usedarray to keep track of which elements have been included in the current permutation.
This is a more space-efficient backtracking approach. Instead of using an auxiliary used array to track which elements have been used, we generate permutations by performing in-place swaps within the input array itself. The key idea is to fix an element at a certain position and then recursively generate all permutations for the remaining part of the array.
Algorithm
- Initialize an empty list
resultto store all permutations. - Define a recursive function
backtrack(first, nums)wherefirstis the index of the element we are trying to place. - Base Case: If
firstis equal tonums.length, it means all elements have been placed. Convert the current state of thenumsarray to a list and add it toresult. Then return. - Recursive Step: Iterate from
i = firsttonums.length - 1. a. Swap the element at indexfirstwith the element at indexi. This places thei-th element into thefirstposition. b. Make a recursive call:backtrack(first + 1, nums)to generate permutations for the rest of the array. c. Backtrack: Swap the elements atfirstandiback to their original positions. This is crucial to restore the array for the next iteration of the loop. - Start the process by calling
backtrack(0, nums). - Return
result.
Walkthrough
The algorithm works by defining a portion of the array that is 'fixed' and a portion that we can still permute. A recursive function, say backtrack(first, nums), is used, where first is the index of the first element in the portion of the array we are currently considering for permutation.
The base case is when first reaches the end of the array (first == nums.length). This implies that all positions have been filled, and the current arrangement of nums is a complete permutation. We convert the array to a list and add it to our results.
In the recursive step, we iterate from the first index to the end of the array. For each index i in this range, we swap the element nums[i] with nums[first]. This action effectively places nums[i] as the first element of the subarray we are permuting. After the swap, we make a recursive call backtrack(first + 1, nums) to generate all permutations for the rest of the array (from first + 1 onwards).
After the recursive call returns, we must backtrack by swapping nums[i] and nums[first] again. This undoes the previous swap, restoring the array to its state before the choice was made. This allows us to explore placing a different element at the first position in the next iteration of the loop.
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(0, nums, result); return result; } private void backtrack(int first, int[] nums, List<List<Integer>> result) { if (first == nums.length) { List<Integer> permutation = new ArrayList<>(); for (int num : nums) { permutation.add(num); } result.add(permutation); return; } for (int i = first; i < nums.length; i++) { // Place i-th integer first in the current permutation swap(nums, first, i); // Use next integers to complete the permutations backtrack(first + 1, nums, result); // Backtrack swap(nums, first, i); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Complexity
Time
O(N * N!)
Space
O(N)
Trade-offs
Pros
More space-efficient as it avoids the O(N) space required for a
usedarray or set.It's an elegant in-place solution that demonstrates a powerful backtracking technique.
Cons
The concept of in-place swapping and backtracking might be slightly less intuitive at first compared to using a
usedflag.This method modifies the array passed into the recursive function. If the original input array needs to be preserved, a copy should be made before starting the process.
Solutions
Solution
public class Solution { public IList < IList < int >> Permute(int[] nums) { var ans = new List < IList < int >> (); var t = new List < int > (); var vis = new bool[nums.Length]; dfs(nums, 0, t, vis, ans); return ans; } private void dfs(int[] nums, int i, IList < int > t, bool[] vis, IList < IList < int >> ans) { if (i >= nums.Length) { ans.Add(new List < int > (t)); return; } for (int j = 0; j < nums.Length; ++j) { if (!vis[j]) { vis[j] = true; t.Add(nums[j]); dfs(nums, i + 1, t, vis, ans); t.RemoveAt(t.Count - 1); vis[j] = false; } } }}class Solution { private List < List < Integer >> ans = new ArrayList <>(); private List < Integer > t = new ArrayList <>(); private boolean [] vis ; private int [] nums ; public List < List < Integer >> permute ( int [] nums ) { this . nums = nums ; vis = new boolean [ nums . length ]; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i == nums . length ) { ans . add ( new ArrayList <>( t )); return ; } for ( int j = 0 ; j < nums . length ; ++ j ) { if (! vis [ j ]) { vis [ j ] = true ; t . add ( nums [ j ]); dfs ( i + 1 ); t . remove ( t . size () - 1 ); vis [ j ] = false ; } } } }/** * @param {number[]} nums * @return {number[][]} */ var permute = function ( nums,) { const n = nums.length; const ans = []; const t = []; const vis = new Array(n).fill(false); function dfs(i) { if (i >= n) { ans.push([...t]); return; } for (let j = 0; j < n; ++j) { if (!vis[j]) { vis[j] = true; t.push(nums[j]); dfs(i + 1); vis[j] = false; t.pop(); } } } dfs(0); return ans;};class Solution {public: vector<vector<int>> permute(vector<int> &nums) { int n = nums.size(); vector<vector<int>> ans; vector<int> t(n); vector<bool> vis(n); function<void(int)> dfs = [&](int i) { if (i == n) { ans.emplace_back(t); return; } for (int 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; }};''' remove an element by its value from a set >>> my_set = {1, 2, 3, 4, 5} >>> my_set.remove(3) >>> print(my_set) {1, 2, 4, 5} ------ cannot remove an element by index from a set in Python3 need to convert the set to a list >>> my_set = {1, 2, 3, 4, 5} >>> my_list = list(my_set) >>> del my_list[2] # remove the element at index 2 >>> my_set = set(my_list) >>> print(my_set) {1, 2, 4, 5} ''' class Solution : # iterative def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: res = [[]] if nums is None or len ( nums ) == 0 : return ans for num in nums : new_res = [] for perm in res : for i in range ( len ( perm ) + 1 ): new_perm = perm [: i ] + [ num ] + perm [ i :] new_res . append ( new_perm ) res = new_res return res ############## class Solution : # iterative, single_perm.insert(index, num) def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: ans = [[]] if nums is None or len ( nums ) == 0 : return ans for num in nums : tmp_list = [] for single_perm in ans : for index in range ( len ( single_perm ) + 1 ): single_perm . insert ( index , num ) tmp_list . append ( single_perm . copy ()) single_perm . pop ( index ) ans = tmp_list return ans ############## ''' In Python 3, both the discard() and remove() methods of a set object are used to remove an element from the set, but there is one key difference: * discard() removes the specified element from the set if it is present, but does nothing if the element is not present. * remove() removes the specified element from the set if it is present, but raises a KeyError exception if the element is not present. >>> a {33, 66, 11, 44, 22, 55} >>> a.discard(22) >>> a {33, 66, 11, 44, 55} >>> a.discard(200) >>> >>> a.remove(200) Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 200 ''' ''' >>> v1 = set([]) >>> v2 = set() >>> >>> v1 set() >>> v2 set() ''' class Solution : def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: res = [] visited = set ([]) def dfs ( nums , path , res , visited ): if len ( path ) == len ( nums ): res . append ( path + []) return for i in range ( 0 , len ( nums )): if i not in visited : visited . add ( i ) path . append ( nums [ i ]) dfs ( nums , path , res , visited ) path . pop () visited . discard ( i ) # remove(i) will throw exception if i not existing dfs ( nums , [], res , visited ) return res ############ class Solution : def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( i ): if i == n : ans . append ( t [:]) return for j in range ( n ): if not vis [ j ]: vis [ j ] = True t [ i ] = nums [ j ] dfs ( i + 1 ) vis [ j ] = False n = len ( nums ) vis = [ False ] * n t = [ 0 ] * n ans = [] dfs ( 0 ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.