Combination Sum

1.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.
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 set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

 1 class Solution {
 2 public:
 3     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 4         sort(candidates.begin(),candidates.end());
 5         vector<vector<int>> result;
 6         vector<int> path;
 7         dfs(0,0,target,candidates,path,result);
 8         return result;
 9     }
10 private:
11     void dfs(int curr,int k,int target,vector<int>& candiates,
12         vector<int>& path,vector<vector<int>>& result){
13         if(curr == target){
14             result.push_back(path);
15             return;
16         }
17 
18         for(int i=k;i<candiates.size();i++){
19             curr = curr+candiates[i];
20             if(curr > target) break;
21             else{
22                 path.push_back(candiates[i]);
23                 dfs(curr,i,target, candiates, path, result);
24                 path.pop_back();
25                 curr = curr - candiates[i];
26             }
27         }
28     }
29 };

2.Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

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 set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

 1 class Solution {
 2 public:
 3      vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
 4         sort(candidates.begin(),candidates.end());
 5         vector<vector<int>> result;
 6         vector<int> path;
 7         dfs(0,0,target,candidates,path,result);
 8         return result;
 9     }
10 private:
11     void dfs(int curr,int k,int target,vector<int>& candiates,
12         vector<int>& path,vector<vector<int>>& result){
13         if(curr == target){
14             if(find(result.begin(),result.end(),path)==result.end())
15                 result.push_back(path);
16             return;
17         }
18 
19         for(int i=k;i<candiates.size();i++){
20             curr = curr+candiates[i];
21             if(curr > target) break;
22             else{
23                 path.push_back(candiates[i]);
24                 dfs(curr,i+1,target, candiates, path, result);
25                 path.pop_back();
26                 curr = curr - candiates[i];
27             }
28         }
29     }
30 };

3.Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

 1 class Solution {
 2 public:
 3     vector<vector<int>> combinationSum3(int k, int n) {
 4         vector<vector<int>> result;
 5         vector<int> path;
 6         dfs(0,1,k,n,path,result);
 7         return result;
 8     }
 9 private:
10     void dfs(int curr,int j,int k,int n,vector<int>& path,
11         vector<vector<int>>& result){
12         if(path.size()==k){
13             if(curr == n){
14                 result.push_back(path);
15             }
16             return;
17         }
18         for(int i=j;i<10;i++){
19             curr = curr + i;
20             if(curr > n) break;
21             else{
22                 path.push_back(i);
23                 dfs(curr, i+1, k, n, path, result);
24                 path.pop_back();
25                 curr = curr - i;
26             }
27         }
28     }
29 };