216. 组合总和 III

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/combination-sum-iii/

题目描述

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

说明：

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

1
2
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

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

分析

这道题和之前几个组合求总和的问题基本思路一致。
本题思路除了基本的递归回溯，还有：

  1. 需要注意递归条件中加了k次
  2. 求总和问题一般需要排序，本题不用，因为1-9已经排好序
  3. 求组合问题需要注意，在递归树的同一层不能出现两个数字一样的分支，所以代码中用pre_nums加以控制。

综合：本题答案为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def __init__(self):
        self.result_all = None
    
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        self.result_all = []
        self.dfs(n, k, 1, [])
        return self.result_all
        
    def dfs(self, n, k, start, result):
        if len(result) == k:
            if sum(result) == n:
                self.result_all.append(result[:])
            return
        pre_nums = []
        for i in range(start, 10):
            if i in pre_nums:
                continue
            if sum(result) + i > n:
                break
            pre_nums.append(i)
            result.append(i)
            self.dfs(n, k, i+1, result)
            result.pop()
        return