Problem:
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
|
1 2 3 4 5 6 |
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] |
Idea:
DFS
Solution:
C++ / set
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua // Runtime: 9 ms class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { set<vector<int>> ans; std::sort(candidates.begin(), candidates.end()); vector<int> curr; dfs(candidates, target, 0, ans, curr); return vector<vector<int>>(ans.begin(), ans.end()); } private: void dfs(const vector<int>& candidates, int target, int s, set<vector<int>>& ans, vector<int>& curr) { if (target == 0) { ans.insert(curr); return; } for (int i = s; i < candidates.size(); ++i) { int num = candidates[i]; if (num > target) return; curr.push_back(num); dfs(candidates, target - num, i + 1, ans, curr); curr.pop_back(); } } }; |
C++ / vector
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua // Runtime: 9ms class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> ans; std::sort(candidates.begin(), candidates.end()); vector<int> curr; dfs(candidates, target, 0, ans, curr); return ans; } private: void dfs(const vector<int>& candidates, int target, int s, vector<vector<int>>& ans, vector<int>& curr) { if (target == 0) { ans.push_back(curr); return; } for (int i = s; i < candidates.size(); ++i) { int num = candidates[i]; if (num > target) return; if (i > s && candidates[i] == candidates[i - 1]) continue; curr.push_back(num); dfs(candidates, target - num, i + 1, ans, curr); curr.pop_back(); } } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment