Leetcode 39 Combination Sum 组合数

 

 

 

 

 

 

解决思路：利用深搜+回溯

这里需要注意两点

1）为了更好的利用深搜，这里对candidates进行从大到小排序；

2）由于candidates中的元素可以重复使用，所以每次深搜都从begin位置开始；

3）target >= nums[i]  这个条件很重要，如果nums[i]  > target，不能使得target == 0.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> item;
        vector<vector<int> > result;
        sort(candidates.begin(), candidates.end()); //进行排序
        dfs(candidates, 0, target, item, result);
        return result;
    }
    void dfs(vector<int>& nums, int begin, int target, vector<int> &item, vector<vector<int> > &result)
    {
        if(target == 0)
        {
            result.push_back(item);
            return;
        }
        for(int i = begin; i < nums.size() && target >= nums[i]; i++)
        {
            item.push_back(nums[i]);
            dfs(nums, i, target - nums[i], item, result);
            item.pop_back();
        }
    }
};