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，就将当前结果放入结果集中