Leetcode:39. 组合总和II
给定一个数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
解题思路:
DFS+回溯法,不同的是,这题同一个元素只能用一次,但可能有重复元素。
回溯:当递归调用DFS时,运行完毕,注意恢复状态,注意路径处理,删除[当前访问位置,end())。
class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); data = candidates; vector<int> road;//存储访问过的值,初始值为空 DFS(0, target, road); return res; } void DFS(int pos, int target, vector<int> road) { if (target == 0) { res.push_back(road); return; } for (int i = pos; i<int(data.size()); i++) { if (data[i] > target) return; target -= data[i]; int pre = road.size(); road.push_back(data[i]); DFS(i + 1, target, road); road.erase(road.begin() + pre, road.end()); target += data[i]; while ((int(data.size())>(i+1))&&(data[i] == data[i + 1])) { i++; } } } private: vector<int> data; vector<vector<int>> res; }; |