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

科技 2024-11-19 10:10 上海

精品推荐：

《征服数据结构》专栏：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<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(ans, new ArrayList<>(), k, n, 1);
    return ans;
}

private void dfs(List<List<Integer>> ans, List<Integer> 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<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(ans, path, k, n, 1);
        return ans;
    }

    void dfs(vector<vector<int>> &ans, vector<int> &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