ChoDocs

外观

LeetCode 216. 组合总和 III ​

作者:Choi Yang
更新于:7 个月前
字数统计:573 字
阅读时长:2 分钟

题目描述 ​

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

说明：

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

javascript
输入: (k = 3), (n = 7);
输出: [[1, 2, 4]];

示例 2:

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

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

解题思路 ​

首先，还是搬运一下大佬的图解，然后我再来解释一番。

参考 xiao_ben_zhu 大佬图解

本题需要一层一层来，第一层我们可以有 i(1-9)个选择，而第二层的每一个值只有 i+1个选择了，因为不能重复。比如你第一次拿了 2，在下一次，你只能从 3开始拿了，如果还是 1的话就会有重复的组合了。这样我们也不用维护 vis数组来去重，因为每一层取的值是不一样的。

javascript
var combinationSum3 = function (k, n) {
  let res = [];
  let dfs = (t, start, sum) => {
    if (t.length === k && sum === n) {
      res.push(t);
    }
    for (let i = start; i < 10; i++) {
      t.push(i);
      dfs(t.slice(), i + 1, sum + i);
      t.pop();
    }
  };
  dfs([], 1, 0);
  return res;
};
cpp
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> t;
        function<void(int, int)> dfs = <CustomLink title="&" href="int start, int sum" /> {
            if (t.size() == k && sum == n) {
                res.push_back(t);
                return;
            }
            for (int i = start; i < 10; i++) {
                t.push_back(i);
                dfs(i + 1, sum + i);
                t.pop_back();
            }
        };
        dfs(1, 0);
        return res;
    }
};
java
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> t = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, k, n);
        return res;
    }
    void dfs(int start, int k, int n) {
        if (t.size() == k && n == 0) {
            res.add(new ArrayList<>(t));
            return;
        }
        for (int i = start; i <= 9; i++) {
            t.add(i);
            dfs(i + 1, k, n - i);
            t.remove(t.size() - 1);
        }
    }
}
python
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        t = []
        def dfs(start, k, n):
            if len(t) == k and n == 0:
                res.append(t[:])
                return
            for i in range(start, 10):
                t.append(i)
                dfs(i + 1, k, n - i)
                t.pop()
        dfs(1, k, n)
        return res
javascript
学如逆水行舟，不进则退

Contributors ​

Choi Yang