目录

1，题目描述

英文描述

中文描述

2，解题思路

3，AC代码

C++

Java

4，解题过程

第一博

---

1，题目描述

原题链接216. 组合总和 III

英文描述

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations. Example 2:

Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations. Example 3:

Input: k = 4, n = 1 Output: [] Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice. Example 4:

Input: k = 3, n = 2 Output: [] Explanation: There are no valid combinations. Example 5:

Input: k = 9, n = 45 Output: [[1,2,3,4,5,6,7,8,9]] Explanation: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 ​​​​​​​There are no other valid combinations.  

Constraints:

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

中文描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。 解集不能包含重复的组合。  示例 1:

输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2:

输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

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

2，解题思路

采用dfs递归+剪枝的方法，借助于堆栈来实现；

sum记录当前的累加和，depth记录当前数组中元素数目，tem记录当前存储的元素（dfs的路径），ans最终答案；

出口：深度depth达到k，函数返回。当sum == n时，将tem加入ans；递归：for(int i = (tem.size() == 0 ? 1 : tem.back() + 1); i <= 9; i++)，将i作为下一个元素，再次进行dfs(sum + i, depth + 1, n, k);剪枝：由于sum只增不减，所以当累加和大于n后，就可以终止for循环中的递归了 （使用break跳出）；

注意dfs中，元素的插入和弹出时机（总是成对执行）； 

过程较为简单，可以直接看代码

3，AC代码

C++

class Solution { public: vector<vector<int>> ans; vector<int> tem; vector<vector<int>> combinationSum3(int k, int n) { dfs(0, 0, n, k); return ans; } void dfs(int sum, int depth, int n, int k) { if(depth == k) { // 数目达到限制（深度即数组中元素数目） if(sum == n) ans.push_back(tem); return; } for(int i = (tem.size() == 0 ? 1 : tem.back() + 1); i <= 9; i++) { if(sum + i > n) break; // 剪枝 由于sum只增不减 当前之和大于n就没必要继续递归下去了 tem.push_back(i); dfs(sum + i, depth + 1, n, k); tem.pop_back(); } } };

Java

Java解法参考@liweiwei1419【回溯 + 剪枝（Java）】

class Solution { public List<List<Integer>> ans = new ArrayList<>(); // 根据官方对 Stack 的使用建议，这里将 Deque 对象当做 stack 使用 // 注意只使用关于栈的接口 public Deque<Integer> path = new ArrayDeque<>(); public List<List<Integer>> combinationSum3(int k, int n) { dfs(0, 0, n, k); return ans; } public void dfs(int sum, int depth, int n, int k) { if(depth == k) { // 数目达到限制（深度即数组中元素数目） if(sum == n) ans.add(new ArrayList<>(path)); return; } for(int i = path.size() == 0 ? 1 : path.getLast() + 1; i <= 9; i++) { if(sum + i > n) break; // 剪枝 由于sum只增不减 当前之和大于n就没必要继续递归下去了 path.addLast(i); dfs(sum + i, depth + 1, n, k); path.removeLast(); } } }

4，解题过程

第一博

dfs递归实现，第一个数num1为[1, 9]（表示从1到9），第二个数num2为[num1 + 1, 9]，······第k个数numk为[numk-1 + 1, 9]；

数据量比较小，所以速度还是很快的