# leetcode 39. Combination Sum (dfs，求所有的组合，和为定值，每个数可以重复用)

Posted by 111qqz on Thursday, April 13, 2017

## TOC

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.
``````

``````/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 00时06分12秒
File Name :39.cpp
************************************************ */
class Solution {
public:

vector<vector<int> >res;
vector<int>tmp;
int n;
//思路：dfs
void dfs( int start,int cur,vector<int> &nums)
{
if (cur==0)
{
res.push_back(tmp);
return ;
}
else if (cur<0) return;
else
{
for ( int i = start ; i < n ; i++)
{
tmp.push_back(nums[i]);
dfs(i,cur-nums[i],nums);
tmp.erase(tmp.begin()+tmp.size()-1);
}
}
}

vector<vector<int>> combinationSum(vector<int>& nums, int target) {
n = nums.size();
if (n==0) return res;
dfs(0,target,nums);
return res;
}
};
``````

「真诚赞赏，手留余香」