LeetCode 39 组合总和

39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

回溯递归实现

相较于 216.组合总和III 本题的重要区别在于：要求从参数序列中进行元素的选取，元素允许重复选取，对选取元素的数量没有要求。

那么依旧是回溯的思想进行，为了实现元素的重复选取，在for循环中选取了当前元素 candidate[cur] 后，进入递归时传递的参数 cur 应当不变，也就保证了在下一层递归中依旧可以选取元素 candidate[cur] ，并且为了防止出现 [2,2,3] 和 [2,3,2] 的情形，每次都从 cur 开始选取。

递归结束的两种条件：

1. target==0 说明选取的元素满足条件。
2. target<0 选取元素已经超过需要

代码实现：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& candidates,int target,int cur){
        if(target==0){
            res.push_back(tmp);
            return ;
        }
        if(target<0) return;
        for(int i=cur;i<candidates.size();i++){
            tmp.push_back(candidates[i]);
            target-=candidates[i];
            DFS(candidates,target,i);
            target+=candidates[i];
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        DFS(candidates,target,0);
        return res;
    }
};

剪枝优化

在此基础上可以进行剪枝优化，若给定的序列candidates是有序的，那么当前可选元素 candidates[cur]>target 时，那么再继续递归将没有意义。因此可以提前结束。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& candidates,int target,int cur){
        if(target==0){
            res.push_back(tmp);
            return ;
        }
        if(target<0||candidates[cur]>target) return;
        for(int i=cur;i<candidates.size();i++){
            tmp.push_back(candidates[i]);
            target-=candidates[i];
            DFS(candidates,target,i);
            target+=candidates[i];
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        DFS(candidates,target,0);
        return res;
    }
};