描述
Given a set of candidate numbers (C) 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:
For example, given candidate set [2, 3, 6, 7]
and target 7
,
A solution set is:
分析
类似于八皇后问题,用的是回溯法。思路是先排序,每次递归把剩下的元素一一加到结果集合中,把剩下的元素放到下一层递归去解决子问题,类似于一个深度优先搜索的过程,这类题目的套路都是一样的。
解决方案1(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 25 26 27
| class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<vector<int>> result; vector<int> path; dfs(candidates, path, result, target, 0); return result; } private: void dfs(vector<int>& candidates, vector<int>& path, vector<vector<int>>& result, int target, int start) { if(target == 0) { result.push_back(path); return; } for(int i = start; i < candidates.size(); i++) { if(candidates[i] > target) { return; } path.push_back(candidates[i]); dfs(candidates, path, result, target-candidates[i], i); path.pop_back(); } } };
|
解决方案2(Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ candidates.sort() result = [] path = [] self.dfs(candidates, path, result, target) return result def dfs(self, candidates, path, result, target): if target == 0: result.append(path[:]) return for item, value in enumerate(candidates): if target < value: return path.append(value) self.dfs(candidates[item:], path, result, target-value) path.pop()
|
解决方案3(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(candidates); backtrack(candidates, result, new ArrayList<>(), 0, target); return result; } private void backtrack(int[] candidates, List<List<Integer>> result, List<Integer> nowList, int left, int target) { if (target == 0) { result.add(new ArrayList<>(nowList)); return; } for (int i = left; i < candidates.length; i++) { if (target < candidates[i]) { return; } nowList.add(candidates[i]); backtrack(candidates, result, nowList, i, target-candidates[i]); nowList.remove(nowList.size()-1); } } }
|
相关问题