[LeetCode]39.Combination Sum
【题目】
Given a set of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.
Thesamerepeated number may be chosen fromCunlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1,a2, … ,ak) must be in non-descending order. (ie,a1≤a2≤ … ≤ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set2,3,6,7
and target7
,
A solution set is:[7]
[2, 2, 3]
【分析】
基本思路是先排好序,然后每次递归中把剩下的元素一一加到结果集合中,并且把目标减去加入的元素,然后把剩下元素(包括当前加入的元素)放到下一层递归中解决子问题。以start记录我们选到了第几个值,并且一直往后选,这样可以避免选到重复的子集。
【代码】
/*********************************
* 日期:2015-01-27
* 作者:SJF0115
* 题目: 39.Combination Sum
* 网址:https://oj.leetcode.com/problems/combination-sum/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// 中间结果
vector<int> path;
// 最终结果
vector<vector<int> > result;
int size = candidates.size();
if(size <= 0){
return result;
}//if
// 排序
sort(candidates.begin(),candidates.end());
// 递归
DFS(candidates,target,0,path,result);
return result;
}
private:
void DFS(vector<int> &candidates, int target,int start,vector<int> &path,vector<vector<int> > &result){
int len = candidates.size();
// 找到一组组合和为target
if(target == 0){
result.push_back(path);
return;
}//if
for(int i = start;i < len;++i){
// 剪枝
if(target < candidates[i]){
return;
}//if
path.push_back(candidates[i]);
DFS(candidates,target-candidates[i],i,path,result);
path.pop_back();
}//for
}
};
int main(){
Solution solution;
int target = 7;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(6);
vec.push_back(7);
vector<vector<int> > result = solution.combinationSum(vec,target);
// 输出
for(int i = 0;i < result.size();++i){
for(int j = 0;j < result[i].size();++j){
cout<<result[i][j]<<" ";
}
cout<<endl;
}
return 0;
}