leetcode 39. Combination Sum (dfs，求所有的组合，和为定值，每个数可以重复用)
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.
题意：给n个数，求所有的组合，和为定值，每个数可以重复用)
思路：。。。。一开始用顺着枚举子集的思路。。。发现。。并不好搞。。。？还不如直接dfs...
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 00时06分12秒
4File Name :39.cpp
5************************************************ */
6class Solution {
7public:
1 vector<vector<int> >res;
2 vector<int>tmp;
3 int n;
4 //思路：dfs
5 void dfs( int start,int cur,vector<int> &nums)
6 {
7 if (cur==0)
8 {
9 res.push_back(tmp);
10 return ;
11 }
12 else if (cur<0) return;
13 else
14 {
15 for ( int i = start ; i < n ; i++)
16 {
17 tmp.push_back(nums[i]);
18 dfs(i,cur-nums[i],nums);
19 tmp.erase(tmp.begin()+tmp.size()-1);
20 }
21 }
22 }
1 vector<vector<int>> combinationSum(vector<int>& nums, int target) {
2 n = nums.size();
3 if (n==0) return res;
4 dfs(0,target,nums);
5 return res;
6 }
7};