🎨Now live: Try our Free AI Image Generation Feature

Description
This function generates all possible permutations of a given list of numbers.
Intuition
The problem can be solved using a depth-first search (DFS) approach by exploring all possible ways to arrange the elements of the list.
Approach
- Define a helper function
dfs
that takes the starting index as an argument. - If the starting index is equal to the length of the list, add the current permutation to the result.
- For each index from the start to the end of the list, swap the current element with the start element.
- Recursively call
dfs
with the next starting index. - Swap back the elements to their original positions to explore other permutations.
- Start the DFS from index 0.
Complexity
Time Complexity:
(O(N \times N!))
- There are (N!) permutations, and creating each permutation takes (O(N)) time.
Space Complexity:
(O(N!))
- The result list stores all permutations, and the recursion depth is (O(N)).
Code
C++
class Solution {
public:
vector> permute(vector& nums) {
vector> result;
function dfs = [&](int start) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
swap(nums[i], nums[start]);
dfs(start + 1);
swap(nums[i], nums[start]);
}
};
dfs(0);
return result;
}
};
Python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def dfs(start):
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
dfs(start + 1)
nums[start], nums[i] = nums[i], nums[start]
dfs(0)
return result
Java
class Solution {
public List> permute(int[] nums) {
List> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums);
return result;
}
private void backtrack(List> result, List tempList, int[] nums) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]);
backtrack(result, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
}
JavaScript
var permute = function(nums) {
let result = []
function dfs (start, curResult) {
if (start === nums.length) {
result.push([...nums])
return;
}
for(let i = start; i< nums.length; i++) {
[nums[i], nums[start]] = [nums[start], nums[i]];
dfs(start + 1, nums);
[nums[i], nums[start]] = [nums[start], nums[i]];
}
}
dfs(0, nums)
return result
};