algorithm - 组合和深度优先搜索解决方案

Question

给定一个正整数列表和一个目标值，生成一个解集。例如，如果列表是 [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

这显然没有给我正确的结果，但我确实认为我在生成解决方案集方面走在正确的轨道上。我根本不明白在递归调用后我需要做什么来删除不必要的元素。

Answer 1

我认为这与您正在尝试做的事情一致:

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 列表中的第一个数字。就这样

1. 将第一个数字附加到答案
2. 将第一个数字添加到 sum
3. 仅从候选列表中删除第一个数字传到下一级

第二个递归调用不使用 candidates 列表中的第一个数字。因为它不使用第一个数字，所以它也不使用第一个数字的任何重复项。这就是 count 变量的原因。 candidates.count(first) 是列表中等于first 的条目数。因此在递归调用中，candidates[count:] 删除了 first 元素和任何重复项。 (这假定列表已排序，这应该在调用 solve 之前完成一次)。