算法题每日一练：组合总和 III

作者：知心宝贝

2023-04-21
江苏
本文字数：1246 字
阅读完需：约 4 分钟

一、问题描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字 1 到 9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

题目链接：组合总和 III

二、题目要求

样例

输入: k = 3, n = 7输出: [[1,2,4]]解释:1 + 2 + 4 = 7没有其他符合的组合了。

复制代码

考察

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

复制代码

三、问题分析

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

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

这一题和我们之前刷的算法题每日一练---第88天：组合总和 II很相似，或者说变得更简单了，因为这一题只允许使用 1~9，不会出现重复的元素，不需要进行判重剪枝操作。

第一式：函数初始

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

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

    vector<int>t;    vector<vector<int>>v;void DFS(int begin,int target,int k)//函数初始

复制代码

第二式：终止条件

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

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

如果 target==0，并且此时数组元素的个数要等于 k，那么就符合终止条件。

if(target==0&&t.size()==k)//终止条件{    v.push_back(t);    return;}

复制代码

第三式：剪枝优化

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

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

if(target<0||t.size()>k)//剪枝优化        return;

复制代码

第四式：递归处理

for(int i=begin;i<=9;i++)//递归处理{    if(i<=target)    {         t.push_back(i);//添加数据         DFS(i+1,target-i,k);         t.pop_back();//回溯    }}

复制代码

每一次如果 i 小于 target，那么就加入数组，目标值减去 i 的值。

模板：

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 begin,int target,int k)//函数初始    {        if(target==0&&t.size()==k)//终止条件        {            v.push_back(t);            return;        }        if(target<0||t.size()>k)//剪枝优化            return;        for(int i=begin;i<=9;i++)//递归处理        {            if(i<=target)            {                t.push_back(i);                DFS(i+1,target-i,k);                t.pop_back();            }        }    }    vector<vector<int>> combinationSum3(int k, int n) {          DFS(1,n,k);//调用回溯函数        return v;    }};