回溯三部曲:
参数输入:nums[],startIndex
终止条件:因为path至少为2,所以path.size()>1
单层搜索逻辑:
同一父节点下的同层上使用过的元素就不能再使用了。
采用回溯算法三部曲
输入nums[]和used[]数组;
终止条件:path.size()==nums.size()
单层循环:使用used[]数组,用过的元素不再用
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int> &nums,vector<bool> &used){
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for(int i = 0; i < nums.size();i++){
if(used[i]==true)continue;
path.push_back(nums[i]);
used[i] = true;
backtracking(nums,used);
used[i] = false;
path.pop_back();
}
}
public :
vector<vector<int>> permute(vector<int> &nums)
{
path.clear();
result.clear();
vector<bool> used(nums.size(), false);
backtracking(nums,used);
return result;
}
};
采用回溯算法三部曲
输入nums[]和used[]数组;
终止条件:path.size()==nums.size()
单层循环:使用used[]数组,用过的元素不再用
本题与上一题区别为nums可能包含重复数字,返回不重复的全排列,故需要进行去重操作,即
nums[i]==nums[i-1]&&used[i-1]==false时continue跳过
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &nums,vector<bool> &used){
if(path.size()==nums.size()){
result.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
continue;
}
if(used[i]==false){
path.push_back(nums[i]);
used[i] = true;
backtracking(nums,used);
used[i] = false;
path.pop_back();
}
}
}
public :
vector<vector<int>> permuteUnique(vector<int> &nums)
{
sort(nums.begin(),nums.end());
vector<bool> used(nums.size(),false);
backtracking(nums,used);
return result;
}
};