算法力扣刷题记录六十四【216.组合总和III】

前言

回溯第二篇。

回顾：上一篇学了回溯的基础知识和模版；组合练习题一应用了一次模版。

本文继续组合问题练习：记录六十四【216.组合总和III】。

一、题目阅读

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

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

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

示例 2:

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

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

2 <= k <= 9
1 <= n <= 60

二、尝试实现

思路【不剪枝】

题目分析：使用数字范围[1,9]，每个数字只能用一次。找一个组合，元素个数是k，求和是n。组合问题：回溯思路。
利用回溯模版开始写递归函数：

递归函数返回值：用vector< int>& temp和vector<vector< int>>& result搜集结果，放到参数里面，无需返回值。所以是void。
递归函数参数：
- int k,int n ,vector< int>& temp和vector<vector< int>>& result已经有4个了；
- int startindex用来确定每一层for循环的开始元素；
- int& sum搜集结果时要判断这个组合之和是否为n，所以用sum来记录。很明显，sum跟随temp回溯。
递归函数终止条件：深度是k，所以temp.size() == k条件一；如果sum==n，那么放入result后return；如果sum!= n，直接return。
递归函数单层逻辑：
- for循环：每一层有几种可能。所以起始元素startindex传入，终止以9结尾。（不剪枝，暴力搜索每一个组合）；
- for循环内部：先放入本层元素；再sum加上放入的元素；递到下一层；回溯temp和sum。（四步）

代码实现

class Solution {
public:void backtracking(int k,int n,int startindex,int& sum,vector<int>& temp,vector<vector<int>>& result){//终止条件if(temp.size() == k && sum != n){//当个数满足但是和不相等时，直接return。return;}if(temp.size() == k&& sum == n){//当个数满足且和相等时，放入最终结果集，再return。result.push_back(temp);return;}for(int i = startindex;i <= 9;i++){temp.push_back(i);//放入本层元素。sum += i;//求和backtracking(k,n,i+1,sum,temp,result);//递到下一层temp.pop_back();//回溯操作。sum -= i;}return;}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> result;vector<int> temp;//放中间结果int sum = 0;backtracking(k,n,1,sum,temp,result);return result;}
};

思路【剪枝】

肯定从和入手，本层剩余加入元素个数：k-temp.size()；剩余和：n-sum。
之后……

三、参考学习

参考学习链接

学习内容

不剪枝的思路和实现就是二、尝试实现；
如何剪枝？

如果sum已经大于n，此时temp.size()还没有等于k，可以直接return，无需进入for循环取值；
要求k个元素，如果选某个元素后，剩余子集大小不足k个，那么这个元素也不能选。所以i <= 9换成i <= 9-(k-temp.size())+1.

代码实现【剪枝】：

class Solution {
public:void backtracking(int k,int n,int startindex,int& sum,vector<int>& temp,vector<vector<int>>& result){//终止条件if(sum > n) return;//剪枝一；if(temp.size() == k && sum != n){//当个数满足但是和不相等时，直接return。return;}if(temp.size() == k&& sum == n){//当个数满足且和相等时，放入最终结果集，再return。result.push_back(temp);return;}for(int i = startindex;i <= 9-(k-temp.size())+1;i++){//剪枝二；temp.push_back(i);//放入本层元素。sum += i;//求和backtracking(k,n,i+1,sum,temp,result);//递到下一层temp.pop_back();//回溯操作。sum -= i;}return;}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> result;vector<int> temp;//放中间结果int sum = 0;backtracking(k,n,1,sum,temp,result);return result;}
};