Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
Related Topics:
Backtracking
Similar Questions:
- Next Permutation (Medium)
- Permutations II (Medium)
- Permutation Sequence (Medium)
- Combinations (Medium)
For a particular DFS level, let start be the index of element we manipulate in this level.
We swap nums[start] with a digit whose index >= start.
After the swap, we DFS one step further, i.e. dfs(nums, start + 1).
Once the children DFS returns, we recover the array by swapping them back.
The exit condition of DFS is when the start index points to the last digit, then we can push the current nums into answers.
The initial call is dfs(nums, 0).
Note that:
- This function doesn't care whether the
numsis sorted. - The permutations generated is NOT in lexigraphical order. For example, if input is
[1,2,3], then output is[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
// OJ: https://leetcode.com/problems/permutations/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N)
class Solution {
vector<vector<int>> ans;
void dfs(vector<int> &nums, int start) {
if (start == nums.size() - 1) {
ans.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
swap(nums[i], nums[start]);
dfs(nums, start + 1);
swap(nums[i], nums[start]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
};// OJ: https://leetcode.com/problems/permutations/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(1)
class Solution {
bool nextPermutation(vector<int> &nums) {
int i = nums.size() - 2, j = nums.size() - 1;
while (i >= 0 && nums[i] >= nums[i + 1]) --i;
if (i >= 0) {
while (j > i && nums[j] <= nums[i]) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
return i >= 0;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans { nums };
while (nextPermutation(nums)) ans.push_back(nums);
return ans;
}
};