16 Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

本质还是一个树结构的遍历搜索，写的过程中感觉自己的知识还是不够扎实。。。

class Solution {
    
public:
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> ans;
        
        //sort vector
        sort(candidates.begin(),candidates.end());
        
        if( candidates.empty() || candidates[0] > target) return ans;
        
        vector<int> vec;
        int sum = 0;
        
        tree(ans,candidates,vec,0,sum,target);
        
        return ans;
        
        
    }
    
    
    void tree(vector<vector<int>>& ans,vector<int>& candidates, vector<int>& vec, int last, int sum, int target)
    {
        
        if(target == sum) 
        {
            ans.push_back(vec);
            return;
        }
     
        for(int i=last;i<candidates.size();i++)
        {

            if(sum + candidates[i] > target) break;
            else
            {
                vec.push_back(candidates[i]);
                tree(ans, candidates, vec, i ,sum+candidates[i], target);
                vec.pop_back();
            }
            
            
        }
 
    }
};

16 Combination Sum

原文：https://www.cnblogs.com/xiaoyisun06/p/11385293.html