专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
据说明年有1200多万毕业生，就业压力也是相当大，为了提升毕业生就业率，教育部发文：严禁校招限定985，211。但我觉得解除限制也提升不了就业率，因为岗位是一定的，毕业人数是一定的，解除限制除了给普通院校学生更多的机会，对提升就业率好像没有什么帮助。
最近一位网友在面试的时候，HR就明确说了，985和211的放一坨，普通院校放一坨，如果985和211都签完了还不够，才会考虑普通院校，主打的就是你限你的，我卡我的，根本不把教育部的文件当回事。。。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第216题：组合总和 III。
问题描述
来源：LeetCode第216题
难度：中等
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
1，只使用数字1到9
2，每个数字 最多使用一次
返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例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 没有其他符合的组合了。
2 <= k <= 9
1 <= n <= 60
问题分析
这题是让从 1 到 9 之间选择 k 个数字，让这 k 个数字之和等于 n ，问有多少这种组合，这实际上是一道回溯算法题。
我们可以把它看作是一棵树，选择元素的过程可以把它看作树的一个分支，如果选择的元素个数大于 k 或者元素的和大于 n 就停止选择。
因为题中说的是组合，不是排列，也就是说[1,2,4]和[1,4,2]是一样的，所以选择当前元素之后下一步只能从他的下一个元素开始，比如示例 2 中的选择如下图所示：
JAVA：
public List
> combinationSum3( int k, int n) { List > ans = new ArrayList<>(); dfs(ans, new ArrayList<>(), k, n, 1); return ans; } private void dfs(List > ans, List path, int k, int n, int start) { if (path.size() >= k || n <= 0) { // 找到一组合适的 if (path.size() == k && n == 0) ans.add( new ArrayList<>(path)); return; } for ( int i = start; i <= 9; i++) { path.add(i); // 选择当前值 dfs(ans, path, k, n - i, i + 1); // 递归 path.remove(path.size() - 1); // 撤销选择 } }C++：
public: vector
> combinationSum3(int k, int n) { vector
> ans; vector
path; dfs(ans, path, k, n, 1); return ans; } void dfs(vector
> &ans, vector
&path, int k, int n, int start) { if (path.size() >= k || n <= 0) { // 找到一组合适的 if (path.size() == k && n == 0) ans.push_back(path); return; } for (int i = start; i <= 9; i++) { path.push_back(i);// 选择当前值 dfs(ans, path, k, n - i, i + 1);// 递归 path.pop_back();// 撤销选择 } }
Python：
def combinationSum3(self, k: int, n: int) -> List[List[int]]: ans = [] path = [] def dfs(total: int, start: int): if len(path) >= k or total <= 0: # 找到一组合适的 if len(path) == k and total == 0: ans.append(path[:]) return for i in range(start, 10): path.append(i) # 选择当前值 dfs(total - i, i + 1) # 递归 path.pop() # 撤销选择 dfs(n, 1) return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。