目录
46. Permutations
方法一、使用used数组回溯
方法二、不使用used数组回溯
47. Permutations II
回溯法
46. Permutations
方法一、使用used数组回溯
class Solution {vector<vector<int>> res;vector<int> apermutation;
public:vector<vector<int>> permute(vector<int>& nums) {vector<int> used(nums.size(),false);backtracking(nums,used);return res;}void backtracking(vector<int>& nums,vector<int> &used){if(apermutation.size() == nums.size()){res.push_back(apermutation);return;}for(int i = 0;i < nums.size();i++){if(used[i])continue;apermutation.push_back(nums[i]);used[i] = true;backtracking(nums,used);apermutation.pop_back();used[i] = false;}}
};方法二、不使用used数组回溯
class Solution {vector<vector<int>> res;
public:vector<vector<int>> permute(vector<int>& nums) {backtracking(nums,0);return res;}void backtracking(vector<int>& nums,int start){if(start == nums.size()){res.push_back(nums);return;}for(int i = start;i < nums.size();i++){swap(nums[i],nums[start]);backtracking(nums,start+1);swap(nums[i],nums[start]);}}
};47. Permutations II
回溯法
class Solution {vector<vector<int>> res;vector<int> apermutaion;
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}void backtracking(vector<int>& nums,vector<bool> &used){if(apermutaion.size() == nums.size()){res.push_back(apermutaion);return;}for(int i = 0;i <nums.size();i++){if(used[i])continue;if(i >0 && nums[i]==nums[i-1] && used[i-1]==false)continue;apermutaion.push_back(nums[i]);used[i] = true;backtracking(nums,used);apermutaion.pop_back();used[i] = false;}}
};
