算法题每日一练 --- 组合总和

2023-04-19
江苏
本文字数：1499 字
阅读完需：约 5 分钟

一、问题描述

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

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

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

题目链接：组合总和

二、题目要求

样例

输入： candidates = [2,3,6,7], target = 7输出： [[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

复制代码

考察

1.回溯算法2.建议用时20~35min

复制代码

三、问题分析

本题是开启回溯算法刷题的第1题，之前没有了解过可以看一下这篇题解，讲解比较详细。

算法题每日一练---第85天：组合

一开始拿到这一题，我想到的是逐渐加上每一个数字，但这种方法远没有 target 逐渐减去一个值，直到为 0 来得巧妙。

第一式：函数初始

我们要初始化一个函数来承载回溯，函数里面的参数如何确定呢？

首先，要传入给定的数组信息，目标值，初始遍历的下标。

vector<int>t;vector<vector<int>>v;void DFS(int start,int target,vector<int>&candidates)//初始信息

复制代码

第二式：终止条件

什么时候结束继续向下开始搜索的条件呢？

题目要求 target 可以由数组的哪些元素组成，每加入一个元素，target 要减去这个元素的值。

如果 target==0，那么就符合终止条件。

if(target==0)//符合要求{     v.push_back(t);     return;}

复制代码

第三式：剪枝优化

这一题剪枝比较简单，上面终止的条件不是等于 0 咩。

那如果 target 已经小于 0，那我们还有必要继续搜索吗，完全没必要。

if(target<0)//剪枝      return;

复制代码

第四式：递归处理

for(int i=start;i<candidates.size();i++)//递归处理{     if(candidates[i]<=target)//加了一个小判断     {         t.push_back(candidates[i]);         DFS(i,target-candidates[i],candidates);         t.pop_back();        }  }

复制代码

上面的代码为啥这样写，我简单讲解一下。

因为题目说数组里面的数字可以重复使用，所以我们 DFS 里面的 i 是没有执行+1操作的。

像上面的执行图一样 7 一直执行-2 操作，最后的叶子结点是-1，开始向上回退一步-3，正好符合条件，存储结果。重复上面的过程就可以了。

模板：

void DFS(变量)//函数初始{    if(条件1||条件2...)//终止条件    {         v.push_back(t);         return;    }    if (条件1||条件2...)//剪枝         return;    for(int i=cur;i<=n;i++)//递归处理    {        //选择当前数字        DFS(向下遍历);        //回退    } }

复制代码

冲冲冲！

四、编码实现

class Solution {public:    vector<int>t;    vector<vector<int>>v;    void DFS(int start,int target,vector<int>&candidates)//函数初始    {        if(target==0)//终止条件        {            v.push_back(t);            return;        }        if(target<0)//剪枝            return;        for(int i=start;i<candidates.size();i++)//递归处理        {            if(candidates[i]<=target)//加了一个小判断            {                t.push_back(candidates[i]);                DFS(i,target-candidates[i],candidates);                t.pop_back();              }          }    }    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {        DFS(0,target,candidates);//导入数据        return v;    }};