米哈游（原神）二面笔试原题。。。

(关注数据结构和算法，了解更多新知识)

来看下今天的算法题，这题是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();// 撤销选择
        }
    }

C：

void dfs(int **ans, int *path, int k, int n, int *returnSize, int *returnColumnSizes, int start, int pathCount) {
    if (pathCount >= k || n <= 0) {
        // 找到一组合适的
        if (pathCount == k && n == 0) {
            ans[(*returnSize)] = malloc(pathCount * sizeof(int));
            memcpy(ans[(*returnSize)], path, pathCount * sizeof(int));
            returnColumnSizes[*returnSize] = pathCount;
            (*returnSize)++;
        }
        return;
    }

    for (int i = start; i <= 9; i++) {
        path[pathCount++] = i;// 选择当前值
        dfs(ans, path, k, n - i, returnSize, returnColumnSizes, i + 1, pathCount);// 递归
        pathCount--;// 撤销选择
    }
}

int **combinationSum3(int k, int n, int *returnSize, int **returnColumnSizes) {
    int **ans = malloc(2001 * sizeof(int *));
    int *path = malloc(9 * sizeof(int));
    *returnColumnSizes = malloc(2001 * sizeof(int));
    *returnSize = 0;
    dfs(ans, path, k, n, returnSize, *returnColumnSizes, 1, 0);
    return ans;
}

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