leetcode 39. Combination Sum

时间：2017-08-09 17:24:22 收藏：0 阅读：161

类似二叉树遍历到根节点path，也类似深度优先搜索

首先保持一个result的vector<vector>，是引用类型。
声明一个保持中间结果的vector，这个vector 始终在变化，在递归中使用
每次让target-candidates[i]，将candidate[i]加入temp中
如果target==0，满足条件将temp加入result 中

但是有两点要注意的：

每次同一个递归层上的temp 要不变，所以将push 进temp，之后要pop出来
因为不能有重复结果，但是每一个candidates又可以用多次，所以在大递归层上，如果考虑了candidates[1]，下次就要考虑candidates[2]. 但是在内部递归时，不需要从下一个节点开始:

class Solution {
    
    
    void comSum(vector<int> &candidates,vector<vector<int>> &result,int s, vector<int> temp, int target)
    {
        if(target==0)
        {
           result.push_back(temp);
            return;
        }
             
        for(int i=s;i<candidates.size();i++)
        {
            if(candidates[i]<=target)
            {
                temp.push_back(candidates[i]);
                
                cout<<candidates[i]<<endl;
                cout<<target<<endl;
            //    int t=temp.size();
             //   temp[t]=candidates[i];
                comSum(candidates, result,s, temp,target-candidates[i]);
                temp.pop_back();
                    
            }
            if(candidates[i]>target)
                return;
            s=s+1;
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> result;
        vector<int> temp;
       comSum(candidates,result,0, temp, target); 
        return result;
    }
};

原文：http://www.cnblogs.com/fanhaha/p/7326446.html