46 全排列
写法一
class Solution {
private:
void dfs(vector<int> &nums, int start, vector<int> &path,vector<vector<int>> &ans){
if(path.size() == nums.size())
ans.push_back(path);
for(int i = start; i < nums.size(); i++){
path.push_back(nums[i]);
swap(nums[start], nums[i]);
dfs(nums, start + 1, path, ans);
swap(nums[start], nums[i]);
path.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
dfs(nums,0,path,ans);
return ans;
}
};
写法二
class Solution {
private:
vector<vector<int>> ans;
void dfs(vector<int>& nums,int idx){
if(idx == nums.size() - 1){
ans.push_back(nums);
return;
}
for(int i = idx; i < nums.size(); i++){
swap(nums[i], nums[idx]);
dfs(nums, idx + 1);
swap(nums[i], nums[idx]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
};