Combination Sum

简介

本篇笔记主要记录,运用DFS或DP算法求解组合数相关题目。

Combination Sum

题目来源:LeetCode 39

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res=[]
candidates.sort()
self.dfs(candidates,target,0,[],res)
return res
def dfs(self,nums,target,index,path,res):
if target<0:
return
if target==0:
res.append(path)
return
for i in range(index,len(nums)):
self.dfs(nums,target-nums[i],i,path+[nums[i]],res)

Combination Sum II

题目来源:LeetCode 40

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
return self.search(candidates, 0 ,target)
def search(self, candidates, start, target):
if target==0:
return [[]]
res=[]
for i in xrange(start,len(candidates)):
if i!=start and candidates[i]==candidates[i-1]:
continue
if candidates[i]>target:
break
for r in self.search(candidates, i+1, target-candidates[i]):
res.append([candidates[i]]+r)
return res

Combination Sum III

题目来源:LeetCode 216

Input: k = 3, n = 9
Output:[[1,2,6], [1,3,5], [2,3,4]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
ans = []
def search(start, cnt, sums, nums):
if cnt > k or sums > n:
return
if cnt == k and sums == n:
ans.append(nums)
return
for x in range(start + 1, 10):
search(x, cnt + 1, sums + x, nums + [x])
search(0, 0, 0, [])
return ans

Combination Sum IV

题目来源:LeetCode 377

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums, combs = sorted(nums), [1] + [0] * (target)
for i in range(target + 1):
for num in nums:
if num > i: break
if num == i: combs[i] += 1
if num < i: combs[i] += combs[i - num]
return combs[target]
分享