Leetcode 77. Combinations 39. Combination Sum

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4], 
]

DFS轻松解决，需要注意的是这个是Combination不是Permutation

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> curr;
    
    if(n == k){
        result.push_back(curr);
        for(int i = 1;i <= k;i++){
            result[0].push_back(i);
        }
        return result;
    }
    
   
    helper(result,curr,1,n,k);
  
    return result;
    
}


void helper(vector<vector<int>>& res,vector<int>& cur,int start,int n,int k){
    if(cur.size() == k){
        res.push_back(cur);
        return ;
    }
    
    for(int i = start;i <= n ;i++){
        if(find(cur.begin(),cur.end(),i) == cur.end()){
            cur.push_back(i);
            helper(res,cur,i + 1,n,k);
            cur.pop_back();
        }    
    }
}

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.
For example, given candidate set [2, 3, 6, 7] and target 7,

A solution set is: 
[
  [7],
  [2, 2, 3]
]

方法和上面那个很相似

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> cur;
    helper(res,cur,candidates,target);
    
    return res;
}

void helper(vector<vector<int>>& res,vector<int>& cur,const vector<int>& info,int sum){
    if(sum == 0){
        
        for(int i = 0;i < res.size();i++){
            if(is_permutation(res[i].begin(),res[i].end(),cur.begin())){
                return ;
            }
        }
        res.push_back(cur);
        return ;
    }   
    
    for(int i = 0;i < info.size();i++){
        if(info[i] <= sum){
            cur.push_back(info[i]);
            helper(res,cur,info,sum - info[i]);
            cur.pop_back();
        }
    }
}