题目描述
忙期末,忙着调大疆的M600已经有快一个月没写算法了。今天回去刷了一下,发现基本废了!这玩意这和数学一样,三天不刷直接废,接下来在忙也要刷一题到三题不然真的白学了。
(天坑的tx2+m600呀,碎碎念调出来还是很有成就感的)
算法1
(dfs+剪枝)
参考文献
https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
(大佬博客的题解写的非常好)懒得开链接的我上个图
C++ 代码
class Solution {
//参考
private:
vector<vector<int>> res;
vector<int> sol;
vector<int> nums;
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
this->nums = nums;
vector<bool> used(nums.size(), false);
dfs(used);
return res;
}
private:
void dfs(vector<bool> used){
if(sol.size() == nums.size()){
res.push_back(sol);
return;
}
for(int i=0; i<nums.size(); i++){
//剪枝条件:i>0 是为了保证num[i-1]有效
//used[i-1] 是因为 num[i-1]在回退的过程中刚刚被撤销了选择
if(used[i] || (i>0 && !used[i-1] && nums[i] == nums[i-1])){//用过了
continue;
}
sol.push_back(nums[i]);
used[i] = true;
dfs(used);
sol.pop_back();
used[i] = false;
}
}
};