崩溃，你限你的，我卡我的。。。

专栏：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算法文档 。