【算法狂想曲】回溯与剪枝 解决 组合总和的问题

2020-03-31   90 次阅读


慢慢刷题有点熟练了也开始做一些以前不会做的题目,这就有一题叫做 组合总和的问题

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。 

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

可以分析一下题目,首先这是一个无重复数字的数组,所以可以尽情放飞自我,一开始看到这个题目我立刻想到了递归回溯,因此代码很快就瞎写出来

class Solution {
public:   
 vector<vector<int>> result;              //储存结果
void backTrace(vector<int>& candidates,int target,vector<int> now,int sum)
{
    if(sum==target)                       //如果总和等于目标,将当前容器添加到结果中
    {
        result.push_back(now);
        return;
    }
    if(sum>target)                         //如果总和大于目标,直接返回
    return;
    for(int i=0;i<candidates.size();i++)   //依次对所有内容进行插入尝试
    {
        now.push_back(candidates[i]);      //插入元素
        backTrace(candidates,target,now,sum+=candidates[i]);                                      //调用
        now.pop_back();                    //弹出元素
        sum-=candidates[i];           
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> now;
        backTrace(candidates,target,now,0);
        return result;
    }
};

结果出来后却跟预期结果有所出入,内容是对了,但是却有赘余
结果

可以看出来第一个结果[2,2,3]而我的结果中多了两个,相当于给[2,2,3]来了一次全排列,,因为题目要求解集不能包含重复的组合,因此这样肯定不行

解决方法

在参考了LeetCode的官方题解后,我注意到了一个词

剪枝

看到他的那张图,我立刻明白了,这题中需要运用到剪枝,将多余的结果剪掉,与其说是剪掉不如说就是避免重复结果的产生

题解中是这样说的

  • 在搜索的时候需要设置搜索起点的下标begin,下一层的节点从这个搜索起点开始搜索
  • 在搜索起点begin之前的数因为以前的分支搜索过了,所以一定会产生重复

瞬间理解了要表达的意思,并修改了代码

AC代码

class Solution {
public:
 vector<vector<int>> result;
//在函数中添加了begin变量用于剪枝
void backTrace(vector<int>& candidates,int target,vector<int> now,int sum,int begin)
{
    if(sum==target)
    {
        result.push_back(now);
        return;
    }
    if(sum>target)
    return;
//从给定的begin开始搜索,以避免产生重复组合
    for(int i=begin;i<candidates.size();i++)
    {
        now.push_back(candidates[i]);
        backTrace(candidates,target,now,sum+=candidates[i],i);
        now.pop_back();
        sum-=candidates[i];
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> now;
        backTrace(candidates,target,now,0,0);
        return result;
    }
};

总结

运行用时和内存消耗的结果不是特别好,只战胜了百分之十几的人,不过AC就好,而且还学到了新知识,以后遇到类似问题就能迎刃而解了
话说之前好像做到过类似的题目没做出来,秒回去做题

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议