Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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:
8
9 vector<vector<int> >res;
10 vector<int>tmp;
11 int n;
12 //思路：dfs
13 void dfs( int start,int cur,vector<int> &nums)
14 {
15 if (cur==0)
16 {
17 res.push_back(tmp);
18 return ;
19 }
20 else if (cur<0) return;
21 else
22 {
23 for ( int i = start ; i < n ; i++)
24 {
25 tmp.push_back(nums[i]);
26 dfs(i,cur-nums[i],nums);
27 tmp.erase(tmp.begin()+tmp.size()-1);
28 }
29 }
30 }
31
32 vector<vector<int>> combinationSum(vector<int>& nums, int target) {
33 n = nums.size();
34 if (n==0) return res;
35 dfs(0,target,nums);
36 return res;
37 }
38};