forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
46-Permutations.cpp
30 lines (27 loc) · 825 Bytes
/
46-Permutations.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
Given array of distinct integers, return all the possible permutations
Ex. nums = [1,2,3] -> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Permute by swapping i/start, DFS from this point, backtrack to undo swap
Time: O(n x n!)
Space: O(n!)
*/
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
dfs(nums, 0, result);
return result;
}
private:
void dfs(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
for (int i = start; i < nums.size(); i++) {
swap(nums[i], nums[start]);
dfs(nums, start + 1, result);
swap(nums[i], nums[start]);
}
}
};