总结下LeetCode上 combination sum problem(未完结)

LeetCode 39. Combination Sum

传送门

题意

给你一个候选集合(全都是正数)和target number,请你从候选集合中找出所有的加和等于target的组合。

思路

One

这种问题最简单的就是backtracking方法,外加一点小小的剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def combinationSum(self, candidates, target):
ans = []
candidates.sort(reverse = True)
def dfs(target,cur,path):
if target == 0:
ans.append(path)
return
for i in range(cur,len(candidates)):
if target - candidates[i] >= 0:
dfs(target - candidates[i],i,path + [candidates[i]])
dfs(target,0,[])
return ans

Another

可以想一下:每个商品可以无限用,同时又要凑出target,那么显然我们可以将该问题想成是一个完全背包的满包问题+记录路径的问题。01背包+记录路径问题
这个和上面的问题稍有偏差。在这里我们不存在最优解,而是有满足条件的所有的解,所以我们需要每次对子结构中满足条件的解进行组合。(由于这里我们对每件商品一次性放完,所以不会存在重复解的情况)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def combinationSum(self, candidates, target):
dp = collections.defaultdict(list)
for val in candidates:
for j in range(val,target + 1):
if j - val == 0:
dp[j].append([val])
else:
tmp = dp[j - val]
for _list in tmp:
l = _list + [val]
dp[j].append(l)
return dp[target]


-------------本文结束感谢您的阅读-------------


本文标题:总结下LeetCode上 combination sum problem(未完结)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2019年05月08日 - 11:05

最后更新:2019年05月08日 - 13:05

原始链接:https://statusrank.xyz/articles/49bf382f.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: