![](https://img.haomeiwen.com/i6745450/e2c88d504dc3e18f.png)
解法一:普通的回溯
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty()) return result;
vector<int> list;
dfs(list, result, nums);
return result;
}
private:
void dfs(vector<int>& list, vector<vector<int>>& result, vector<int> nums){
if(list.size() == nums.size()){
result.push_back(list);
return;
}
for(int i = 0; i < nums.size(); i++){
if(find(list.begin(), list.end(), nums[i]) != list.end()){
continue;
}
list.push_back(nums[i]);
dfs(list, result, nums);
list.pop_back();
}
}
};
或使用数组used[]来记录
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty()) return result;
vector<int> list;
vector<bool> used(nums.size(), false);
dfs(list, result, nums, used);
return result;
}
private:
void dfs(vector<int>& list, vector<vector<int>>& result, vector<int> nums, vector<bool> used){
if(list.size() == nums.size()){
result.push_back(list);
return;
}
for(int i = 0; i < nums.size(); i++){
if(!used[i]){
used[i] = true;
list.push_back(nums[i]);
dfs(list, result, nums, used);
list.pop_back();
used[i] = false;
}
}
}
};
解法二:使用交换的思想
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty()) return result;
vector<int> list;
permuteHelper(result, nums, 0);
return result;
}
private:
void permuteHelper(vector<vector<int>>& result, vector<int>& nums, int begin){
if(begin >= nums.size()){
result.push_back(nums);
return;
}
for(int i = begin; i < nums.size(); i++){
swap(nums[i], nums[begin]);
permuteHelper(result, nums, begin+1);
swap(nums[i], nums[begin]);
}
}
};
https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
![](https://img.haomeiwen.com/i6745450/8bc54fbbd5813ed5.png)
网友评论