Problem:
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
|
1 2 3 4 |
[ [7], [2, 2, 3] ] |
Idea:
DFS
Solution: C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ans; vector<int> cur; std::sort(candidates.begin(), candidates.end()); dfs(candidates, target, 0, cur, ans); return ans; } private: void dfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans) { if (target == 0) { ans.push_back(cur); return; } for (int i = s; i < candidates.size(); ++i) { if (candidates[i] > target) break; cur.push_back(candidates[i]); dfs(candidates, target - candidates[i], i, cur, ans); cur.pop_back(); } } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
""" Author: Huahua Runtime: 75 ms (batter than 97.04%) """ class Solution(object): def combinationSum(self, candidates, target): def dfs(candidates, target, s, curr, ans): if target == 0: ans.append(curr[:]) return for i in xrange(s, len(candidates)): if candidates[i] > target: return curr.append(candidates[i]) dfs(candidates, target - candidates[i], i, curr, ans) curr.pop() ans = [] candidates.sort() dfs(candidates, target, 0, [], ans); return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment