【小白爬Leetcode39】数组总和 Combination Sum

题目

Leetcode39 $\color{#ffaa00}{medium}$medium
点击进入原题链接：数组总和 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.

方法一 暴力搜索（不完全递归）

我的想法是：

1. 递归函数DFS每一层都把数字candidates[i]所有选择次数的可能性全部搜索完，start就表示当前递归是从哪一个数字开始往后选择（前面的数字都在上层的递归中讨论过了），直到递归到叶子节点(start==candidates.size()-1)。
2. 在每一层递归中，用一个while循环遍历这个数字candidates[i]可以被选择几次（1次，2次，3次…0次则包含在后面的循环中），直到sum大于target。
3. 在每一次while循环里，调用下一层递归，也就是candidates[i]被选择了n次的情况下，再继续选择candidates[i+1]以及后面的数字。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int len = candidates.size();
        vector<int> candidates_cur; //用来记录当前路径
        DFS(candidates,target,0,0,candidates_cur);
        return this->ans;
    }
private:
    vector<vector<int>> ans;
    void DFS(vector<int>& candidates,const int& target,int sum,int start,vector<int> candidates_cur){
    	//sum是当前达到的总和，start表示start之前的组合都被尝试过了，candidates_cur记录当前路径
        for(int i=start;i<candidates.size();i++){ //从start开始
            int sum_tmp = sum; //拷贝一下sum待用
            vector<int> candidates_tmp = candidates_cur;//拷贝一下当前路径待用
            //遍历candidates[i]所有可取的数量，直到sum_tmp>target
            while(sum_tmp<=target){ //当sum还没有达到累加值时候
                if(sum_tmp==target){ //满足sum == target 就把路径加入到
                    this->ans.emplace_back(candidates_tmp);
                    break;
                }
                sum_tmp += candidates[i]; //继续叠加candidataes[i]
                candidates_tmp.emplace_back(candidates[i]); //相应地路径也要加上
                if(sum_tmp<target) DFS(candidates,target,sum_tmp,i+1,candidates_tmp); //往下一个数字尝试
            }
        }
    }
};

可以看到，效率十分地低下，因为这里的递归函数vector<int> candidates_cur传的是拷贝而不是引用，所以每一次递归都需要O(k)的时间来拷贝 candidates_cur（k是candidates_cur的长度），同时花费额外的栈空间。由于每一层递归都含有一个while循环，sum在每一层循环中需要积累，以便下一次循环使用，即sum无法减回去进行回溯，同理candidates_tmp也是这样。因此这是个彻彻底底的暴力搜索而不是回溯，无论是否遇到正确达到都进行拷贝数组，效率十分低下。

改进一

在这个基础上进行改进，采用传引用的方式，为了更方便地回溯，把while循环改成了for循环，更好地掌控循环的次数。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int len = candidates.size();
        vector<int> candidates_cur; //用来记录当前路径
        DFS(candidates,target,0,candidates_cur);
        return this->ans;
    }
private:
    vector<vector<int>> ans;
    void DFS(vector<int>& candidates,int target,int start,vector<int>& candidates_cur){
    	//sum是当前达到的总和，start表示start之前的组合都被尝试过了，candidates_cur记录当前路径
        if(target==0){
            this->ans.emplace_back(candidates_cur);
            return;
        }
        for(int i=start;i<candidates.size();i++){ //从start开始
            //遍历candidates[i]所有可取的数量，直到sum_tmp>target
            int most_num = target/candidates[i];
            for(int j=1;j<=most_num;j++){
                target -= candidates[i];
                candidates_cur.emplace_back(candidates[i]);
                DFS(candidates,target,i+1,candidates_cur);
            }
            for(int j=1;j<=most_num;j++){
                target += candidates[i];
                candidates_cur.pop_back();
            }
        }
    }
};

seems better…

改进二

如果先对candidates数组进行排序，如果前面的数字都已经使得target<0了，那么后面更大的数字就没有必要再遍历了。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int len = candidates.size();
        sort(candidates.begin(),candidates.end(),less<int>());
        vector<int> candidates_cur; //用来记录当前路径
        DFS(candidates,target,0,candidates_cur);
        return this->ans;
    }
private:
    vector<vector<int>> ans;
    void DFS(vector<int>& candidates,int target,int start,vector<int>& candidates_cur){
    	//sum是当前达到的总和，start表示start之前的组合都被尝试过了，candidates_cur记录当前路径
        if(target==0){
            this->ans.emplace_back(candidates_cur);
            return;
        }
        for(int i=start;i<candidates.size();i++){ //从start开始
            //遍历candidates[i]所有可取的数量，直到sum_tmp>target
            if(target-candidates[i]<0) break; //后面的数字更大，不用看了肯定不行
            int most_num = target/candidates[i];
            for(int j=1;j<=most_num;j++){
                target -= candidates[i];
                candidates_cur.emplace_back(candidates[i]);
                DFS(candidates,target,i+1,candidates_cur);
            }
            for(int j=1;j<=most_num;j++){
                target += candidates[i];
                candidates_cur.pop_back();
            }
        }
    }
};

方法二 二进制遍历回溯

回溯的精髓就是传引用，在同一片地址上进行操作，每次的试错成本仅仅是把试错后的变量复原成试错前的，而不是每次是错都把变量拷贝一遍。

【二进制遍历】这道题可以采用经典的二进制遍历遍历，时间复杂度为O(2ⁿ)，即每一个元素都考虑选/不选两种情况，一共n个元素，因此是有n个2相乘。关于二进制遍历，有两种方式实现：

• 循环实现： 大多采用位运算的方式。1<<n，即 2ⁿ。由于这道题的穷举有对错之分（满足sum==target才是正确的穷举），需要回溯来减少时间开销，所以不适合这种方式。
• 递归实现： 就是这道题要采用的形式。一般来说，回溯就是建立在递归实现的基础上，回溯+二进制遍历就构成了本题的一个经典模板。不过有一点需要变通一下，就是本题允许一个数字选择多次，也就是对于一个数子来说，状态不止选/不选两种，还有选多少个的问题，这个需求可以通过改变一下规则：“选择当前元素后，下一次递归可以选择当前元素” 来实现。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int len = candidates.size();
        vector<int> candidates_cur;
        DFS(candidates,target,0,candidates_cur);
        return this->ans;
    }
private:
    vector<vector<int>> ans;
    void DFS(vector<int>& candidates, int target,int idx,vector<int>& candidates_cur){
        //target表示当前距离题目要求的总和还差多少，idx表示当前递归选择的是哪一个递归,candidates_cur表示当前路径
        if(idx==candidates.size()) return; //叶子节点
        if(target==0){ //符合条件的
            this->ans.emplace_back(candidates_cur);
            return;
        }
        //不选当前元素
        DFS(candidates,target,idx+1,candidates_cur);
        //选择当前元素
        if(target-candidates[idx]>=0){ //防止出现target为负的情况
            candidates_cur.emplace_back(candidates[idx]);
            DFS(candidates,target-candidates[idx],idx,candidates_cur); //注意idx不能+1，保证下一层递归还能选idx
            candidates_cur.pop_back();
        }
    }
};

方法三 剪枝

把candidates升序排序，如果当前target都小于0了，后面更就不用看了（后面数字更大）。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int len = candidates.size();
        sort(candidates.begin(),candidates.end(),less<int>()); //对candidates进行升序排列
        vector<int> candidates_cur;
        DFS(candidates,target,0,candidates_cur);
        return this->ans;
    }
private:
    vector<vector<int>> ans;
    void DFS(vector<int>& candidates, int target,int idx,vector<int>& candidates_cur){
        //target表示当前距离题目要求的总和还差多少，idx表示当前递归选择的是哪一个递归,candidates_cur表示当前路径
        if(idx==candidates.size()) return; //加过头了
        if(target==0){
            this->ans.emplace_back(candidates_cur);
            return;
        }
        if(target-candidates[idx]>=0){
            //不选当前元素
            DFS(candidates,target,idx+1,candidates_cur);
            //选择当前元素
            candidates_cur.emplace_back(candidates[idx]);
            DFS(candidates,target-candidates[idx],idx,candidates_cur); //注意idx不能+1，保证下一层递归还能选idx
            candidates_cur.pop_back();
        }
    }
};