组合总和II
和39的区别是不能重复使用元素
回溯（无去重，超时）
无去重，只能在最后加入时候find查找是否存在一样，再加入
class Solution { public: vector<vector<int>> result; vector<int> path; void backtarcking(vector<int>& candidates, int target , int sum ,int indnx) { if(sum > target)return; if(sum == target) { auto it = find(result.begin(),result.end(),path); if(it == result.end() ) result.push_back(path); return; } for(int i=indnx ; i < candidates.size() && sum + candidates[i] <= target ; i++) { path.push_back(candidates[i]); backtarcking(candidates,target,sum+candidates[i],i+1); path.pop_back(); } return; } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); backtarcking(candidates,target,0,0); return result; } };
回溯去重
去重：在同一层上，值一样的元素只能用一次。同一枝上可以多次用
class Solution { public: vector<vector<int>> result; vector<int> path; void backtarcking(vector<int>& candidates, int target , int sum ,int indnx) { if(sum > target)return; if(sum == target) { result.push_back(path); return; } for(int i=indnx ; i < candidates.size() && sum + candidates[i] <= target ; i++) { //发现一样的元素这一层已经用过了，直接跳过这次 if(i > indnx && candidates[i] == candidates[i-1]) continue; path.push_back(candidates[i]); backtarcking(candidates,target,sum+candidates[i],i+1); path.pop_back(); } return; } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); backtarcking(candidates,target,0,0); return result; } };
二刷
class Solution { public: vector<int> path; vector<vector<int>> result; int sum = 0; void dfs(vector<int>& candidates, int target ,int indnx) { if(sum > target) return; if(sum == target) { if(find(result.begin(),result.end(),path) == result.end()) result.push_back(path); return; } for(int i=indnx ; i<candidates.size() && sum + candidates[i] <= target ; i++) { if(i > indnx && candidates[i] == candidates[i-1]) continue; path.push_back(candidates[i]); sum += candidates[i]; dfs(candidates,target,i+1); sum -= candidates[i]; path.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); dfs(candidates,target,0); return result; } };
