Leetcode 216:组合总和 III(最详细的解法!!!)

找出所有相加之和为 nk 个数的组合组合中只允许含有 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]]

解题思路

这个问题是之前问题的衍生,而且比之前的问题容易,我们只要在原有的基础上稍加修改即可。

Leetcode 39:组合总和(最详细的解法!!!)

Leetcode 40:组合总和 II(最详细的解法!!!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
result = list()
nums = [i for i in range(1, 10)]
self._combinationSum3(nums, n, 0, list(), result, k)
return result

def _combinationSum3(self, nums, target, index, path, res, k):
if target == 0 and len(path) == k:
res.append(path)
return

if path and target < path[-1]:
return

for i in range(index, len(nums)):
self._combinationSum3(nums, target-nums[i], i + 1, path+[nums[i]], res, k)

我们仅仅增加了一个len(path) == k

同样的,对于递归可以解决的问题,我们都应该思考是不是可以通过迭代解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def combinationSum3(self, k, n):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = [i for i in range(1, 10)]
result = list()
stack = [(0, list(), n)]
cand_len = len(candidates)

while stack:
i, path, remain = stack.pop()
while i < cand_len:
if path and remain < path[-1]:
break
if candidates[i] == remain and len(path) == k - 1: # add
result.append(path + [candidates[i]])
stack += [(i + 1, path + [candidates[i]], remain - candidates[i])]
i+=1

return result

同样也只是一点小小的修改。

这个问题有一个非常pythonic的解法,使用itertools.combinations

1
2
3
4
5
6
7
8
class Solution(object):
def combinationSum3(self, k, n):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
return [x for x in itertools.combinations(range(1, 10), k) if sum(x) == n]

当然我们这里也可以写出基于combinations的版本,大家可以试试!!!

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!