Dare2Solve
This function generates all possible permutations of a given list of numbers.
The problem can be solved using a depth-first search (DFS) approach by exploring all possible ways to arrange the elements of the list.
dfs
that takes the starting index as an argument.dfs
with the next starting index.(O(N \times N!))
(O(N!))
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
function<void(int)> 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;
}
};
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
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> 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);
}
}
}
}
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
};