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

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 列表中的第一个数字。所以它

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

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

Answer 2

这是一个使用递归的可能解决方案——我选择了一个元组来表示组合，但你也可以使用列表来表示这些组合

def combinationSum (l, target, sum = 0, comb = ()):

  # base case: empty input [l]
  if not l:
    return []

  # inductive case: [l] has at least one element
  else:

    # [x] is the first sub-problem
    # [xs] is the rest of the sub-problems
    x, *xs = l

    # [x] plus [sum] is bigger than [target]
    if x + sum > target:
      return \
        combinationSum (xs, target, sum, comb)

    # [x] plus [sum] is smaller than [target]
    elif x + sum < target:
      return \
        combinationSum (xs, target, sum + x, (x, *comb)) + \
        combinationSum (xs, target, sum, comb)

    # [x] plus [sum] is equal to [target]
    else:
      return \
        [ (x, *comb)  ] + \
        combinationSum (xs, target, sum + x, (x, *comb)) + \
        combinationSum (xs, target, sum, comb)

data = [10, 1, 2, 7, 6, 1, 5]

print (combinationSum (data, 8))
# [(5, 2, 1), (7, 1), (1, 6, 1), (6, 2), (5, 1, 2), (1, 7)]

如果您希望combinationSum允许重复值，您只需更改一部分。请注意，程序将例如 (5, 1, 1, 1) 视为一个解决方案 3 次，因为 1 出现在 3 个不同的位置。如果您只想 (5, 1, 1, 1) 出现一次，则必须考虑其他方法。

...
    elif x + sum < target:
      return \
        <del>combinationSum (xs, target, sum + x, (x, *comb)) + \</del>
        combinationSum (<b>l</b> , target, sum + x, (x, *comb)) + \
        combinationSum (xs, target, sum, comb)
...

print (combinationSum (data, 8))
# [ (1, 1, 1, 1, 1, 1, 1, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (2, 1, 1, 1, 1, 1, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (1, 2, 1, 1, 1, 1, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (2, 2, 1, 1, 1, 1)
# , (1, 1, 2, 1, 1, 1, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (1, 2, 2, 1, 1, 1)
# , (1, 1, 1, 2, 1, 1, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (5, 1, 1, 1)
# , (2, 2, 2, 1, 1)
# , (1, 1, 2, 2, 1, 1)
# , (1, 1, 1, 1, 2, 1, 1)
# , (6, 1, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (5, 1, 1, 1)
# , (1, 2, 2, 2, 1)
# , (1, 1, 1, 2, 2, 1)
# , (1, 1, 1, 1, 1, 2, 1)
# , (5, 2, 1)
# , (7, 1)
# , (1, 6, 1)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (5, 1, 1, 1)
# , (2, 2, 2, 2)
# , (1, 1, 2, 2, 2)
# , (1, 1, 1, 1, 2, 2)
# , (6, 2)
# , (1, 1, 1, 1, 1, 1, 2)
# , (5, 1, 2)
# , (1, 7)
# , (1, 1, 6)
# , (1, 1, 1, 1, 1, 1, 1, 1)
# , (5, 1, 1, 1)]
# ]

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

Combinations sum depth first search solution

algorithm

recursion

depth-first-search