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