跳转至

LeetCode: 216. 组合总和 III

1、题目描述

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

说明:

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

示例 1:

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

示例 2:

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

2、解题思路

​ 题目里面要求每种组合不包含重复数字,1-9的组合数可以直接使用库函数来求出来

class Solution:
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        result = []

        for i in itertools.combinations(range(1, 10), k):
            if sum(i) == n:
                result.append(list(i))

        return result

​ 还有一个思路,深度优先搜索,从1开始,假如和是5,那么从1开始判断,如果找到和是5的了,就将组合加进去,没找到的话,就去掉,如果是使用和的形式,判断和小于0,就表示不存在,返回

​ 如果等于0,就将当前结果放入结果集中