给定一个正整数列表和一个目标值,生成一个解集。例如,如果列表是 [10, 1, 2, 7, 6, 1, 5]
并且目标是 8
,则解集是...
[
[1, 7],
[1, 2, 5],
[2, 6]
[1, 1, 6]
[
我知道对此有多种解决方案,例如 dp,但我正在尝试让我的 dfs 解决方案正常工作,我相信我已经非常接近了,但我就是无法获得正确的结果。如果可能的话,我希望您不要过多更改我的初始答案,如果那不可能,任何解决方案都可以。
def combinationSum(self, candidates, target):
candidates.sort()
total = []
self.helper(candidates, 0, target, [], total)
def helper(self, candidates, curr, target, temp, total):
if target == 0:
total.append(temp)
return
if target < 0:
return
for i in range(curr, len(candidates)):
# avoid duplicates
if i > curr and candidates[i] == candidates[i-1]:
continue
temp.append(candidates[i])
self.helper(candidates, i+1, target-candidates[i], temp, total)
# I'm not sure what to do here
这显然没有给我正确的结果,但我确实认为我在生成解决方案集方面走在正确的轨道上。我根本不明白在递归调用后我需要做什么来删除不必要的元素。
最佳答案
我认为这与您正在尝试做的事情一致:
def solve(target, sum, candidates, answer):
if sum == target:
print answer
return
if len(candidates) == 0 or sum > target:
return
first = candidates[0]
count = candidates.count(first);
answer.append(first)
solve(target, sum+first, candidates[1:], answer) #using the current number
answer.pop()
solve(target, sum, candidates[count:], answer) #skipping the current number and any duplicates
if __name__ == "__main__":
candidates = [10, 1, 2, 7, 6, 1, 5]
candidates.sort();
solve(8, 0, candidates, [])
关键是 solve
有两个递归调用。
第一个递归调用使用 candidates
列表中的第一个数字。就这样
- 将第一个数字附加到答案
- 将第一个数字添加到
sum
- 仅从候选列表中删除第一个数字 传到下一级
第二个递归调用不使用 candidates
列表中的第一个数字。因为它不使用第一个数字,所以它也不使用第一个数字的任何重复项。这就是 count
变量的原因。 candidates.count(first)
是列表中等于first
的条目数。因此在递归调用中,candidates[count:]
删除了 first
元素和任何重复项。 (这假定列表已排序,这应该在调用 solve
之前完成一次)。
关于algorithm - 组合和深度优先搜索解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49248668/