216.组合总和III

链接：216.组合总和III
难度：Medium
标签：数组、回溯
简介：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

题解 1 - typescript

• 编辑时间：2020-09-11
• 执行用时：76ms
• 内存消耗：37.7MB
• 编程语言：typescript
• 解法介绍：回溯递归。

function combinationSum3(k: number, n: number): number[][] {
  const ans: number[][] = [];
  const used: number[] = [];
  dfs(k, n);
  return ans;
  function dfs(count: number, sum: number): void {
    if (count === 1) {
      if (sum >= 1 && sum <= 9 && sum > used[used.length - 1]) ans.push([...used, sum]);
      return;
    }
    const max = used[used.length - 1] || 0;
    for (let i = max + 1; i <= 9; i++) {
      if (used.includes(i)) continue;
      used.push(i);
      dfs(count - 1, sum - i);
      used.pop();
    }
  }
}

题解 2 - python

• 编辑时间：2024-04-21
• 执行用时：42ms
• 内存消耗：16.42MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        def dfs(num: int, k: int, n: int, arr: List[int]):
            if k == 0:
                if arr and n == 0:
                    res.append(arr[:])
            elif n < 0: return
            elif num == 10: return
            else:
                arr.append(num)
                dfs(num + 1, k - 1, n - num, arr)
                arr.pop()
                dfs(num + 1, k, n, arr)
        dfs(1, k, n, [])
        return res