首页 > 代码库 > 39. Combination Sum
39. Combination Sum
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:
- 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:
[ [7], [2, 2, 3]]
采用深度优先搜索的思想，对于输入candidates=[1,2] ，target=3，遍历的方向如图：
1 #include "stdafx.h" 2 3 #include <iostream> 4 #include <vector> 5 #include <algorithm> 6 7 using namespace std; 8 void helper(int pos, int base, int target, vector<int>& candidates, vector<int>& path, vector<vector<int> >& result) 9 {10 if (base > target)11 return;12 if (base == target)13 {14 result.push_back(path);15 return;16 }17 for (int i = pos; i < candidates.size(); ++i)18 {19 path.push_back(candidates[i]);20 helper(i, base + candidates[i], target, candidates, path, result);21 path.pop_back();22 }23 24 }25 vector<vector<int> > combinationSum(vector<int>& candidates, int target)26 {27 vector<vector<int> > result;28 vector<int> path;29 sort(candidates.begin(), candidates.end());30 vector<int>::iterator it = unique(candidates.begin(),candidates.end());31 candidates.erase(it, candidates.end());32 helper(0, 0, target, candidates, path, result);33 return result;34 }35 int main()36 {37 vector<vector<int> > result;38 vector<int> candidates;39 candidates.push_back(2);40 candidates.push_back(2);41 candidates.push_back(3);42 candidates.push_back(7);43 int target = 7;44 result = combinationSum(candidates, target);45 46 return 0;47 }
39. Combination Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。