欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-24 12:45:00
...

题目

Leetcode39 medium\color{#ffaa00}{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.

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

方法一 暴力搜索(不完全递归)

我的想法是:

  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); //往下一个数字尝试
            }
        }
    }
};

【小白爬Leetcode39】数组总和 Combination Sum
可以看到,效率十分地低下,因为这里的递归函数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…
【小白爬Leetcode39】数组总和 Combination Sum

改进二

如果先对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();
            }
        }
    }
};

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

方法二 二进制遍历回溯

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

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

  • 循环实现: 大多采用位运算的方式。1<<n,即 2n。由于这道题的穷举有对错之分(满足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();
        }
    }
};
相关标签: 小白爬LeetCode