在 Python 中查找总和为给定值的子数组

Question

如果给我一个子数组 [1,2,3,4] 和一个值 8。我想 return 子数组 [1,3,4]。我的代码中有一个错误，并且不确定如何修复它，因为我是递归的新手。我的 Python 代码如下。我正在取回要打印的值 [3,4]，这显然不是正确答案。如何获取数组中的第一个元素？

def main():
    s = 0
    a = [1,2,3,4] # given array
    sa = [] # sub-array
    w = 8 # given weight
    d = False
    d, sa = checkForWeight(a,w,s,d,sa)
    print sa

def checkForWeight(a,w,s,d,sa):
    l = len(a)
    s += a[0]
    sa.append(a[0])
    if s == w:
        d = True
        return d, sa
    else:
        try:
            d, sa = checkForWeight(a[1:],w,s,d,sa)
            if d != True:
                d, sa = checkForWeight(a[2:],w,s,d,sa)
            else:
                return d, sa
        except:
            sa = [] # i put this here because I want to erase the incorrect array
    return d, sa

Answer 1

您需要任何子数组来匹配您的总和吗？或者 all 子数组？（或者最短，或者最长？）正确的答案将高度依赖于此。

顺便说一句，这是背包问题的变体：https://en.wikipedia.org/wiki/Knapsack_problem

此外，您的递归策略似乎是复杂性的阶乘。（如果是代码测试，仅此一项就很可能会让申请人失败。）我强烈建议使用动态编程方法。

编辑

如果你需要所有可能的，你正在看一个 NP 问题。我建议关注 implementation/maintenance 的易用性而不是绝对性能来炫耀您的技能。例如：

import itertools

def find_all_subsets_that_sum(elements, total):
  for i in range(len(elements)):
    for possible in itertools.combinations(elements, i+1):
      if sum(possible)==total:
        yield possible

print list(find_all_subsets_that_sum([1,2,3,4,5,6,7,8,9,10], 10))

不是绝对最快的（您可以在自滚动递归解决方案中进行大量修剪），但它与您提出的任何更复杂的解决方案一样大。（所有解决方案都将由 O(n choose n/2) 支配。）很少有面试候选人会这样回答：

This is not as fast as it can be, but it's within spitting distance of the fastest, and would likely be the best ROI on developer hours, in both implementation and maintenance. Unless of course the data set we're parsing is huge, in which case i would recommend relaxing the requirements to returning a heuristic of some number of solutions that could be calculated with a O(n^2) dynamic programming solution."

您可以利用它脱颖而出。

Answer 2

直接的问题是您在函数顶部将 a[0] 附加到 sa，但随后使用子调用中的 return 值将其销毁。要修补此问题，请在 return 最终结果之前添加一个子句：

    except:
        sa = [] # i put this here because I want to erase the incorrect array
if d:
    sa = [a[0]] + sa
print "Leave: drop", d,sa
return d, sa

我确实建议您遵循评论中的建议：与其传递那么多东西，不如集中精力对部分解决方案进行本地控制。

尝试两种解决方案：使用和不使用当前元素。您的递归调用将如下所示：

sa = checkForWeight(a[1:], w)         # Solutions without first element
    -- and --
sa = checkForWeight(a[1:], w-a[0])    # Solutions using first element

You don't have to return a success flag; if **sa** is None or empty, the call failed to find a solution.  If it succeeded, in the **w-a[0]** call, then you also need to prepend each solution in **sa** with **a[0]**.

这让你感动吗？

Answer 3

我做了一个可行的递归解决方案，希望对您有所帮助：

def main():
    success, solution = WeightChecker((1,2,3,4)).check(8)
    print solution

class WeightChecker(object):
    def __init__(self, to_check):
        self._to_check = to_check
    def check(self, weight):
        return self._check((), 0, weight)
    def _check(self, current_solution, index_to_check, remaining_weight):
        if remaining_weight == 0:
            return True, current_solution
        if index_to_check == len(self._to_check):
            return False, ()
        current_check = self._to_check[index_to_check]
        success, solution = self._check(current_solution + (current_check, ), index_to_check + 1, remaining_weight - current_check)
        if not success:
            success, solution = self._check(current_solution, index_to_check + 1, remaining_weight)
        return success, solution

（动态规划方法更好，正如 keredson 所建议的那样）

在 Python 中查找总和为给定值的子数组

Find subarray that sums to given value in Python

python

recursion

sub-array