Find subarray that sums to given value in Python
<p>If I am given a subarray [1,2,3,4] and a value 8. I want to return the subarray [1,3,4]. I have a bug in my code and am not sure how to fix it since I am new to recursion. I have my Python code below. I am getting back the value [3,4] to print which is obviously not the correct answer. How do I get my first element in the array?</p>

<pre><code>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
</code></pre>

<p>Do you need <strong>any</strong> subarray that matches your sum?  or <strong>all</strong> subarrays?  (Or the shortest, or the longest?)  The proper answer is going to be highly dependent on this.</p>

<p>BTW, this is a varient of the knapsack problem: <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">https://en.wikipedia.org/wiki/Knapsack_problem</a></p>

<p>Also, your recursive strategy appears to be factorial in complexity.  (If it were for a code test, this alone would likely fail the applicant.)  I'd highly suggest a dynamic programming approach.</p>

<p><strong>EDIT</strong></p>

<p>If you need all possible, you're looking at an NP problem.  I'd recommend focusing on ease of implementation/maintenance rather than absolute performance to show off your skills.  For example:</p>

<pre><code>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))
</code></pre>

<p>Is not the absolute fastest (you could do a lot of pruning in a self-rolled recursive solution), but it'll be the same big-O as whatever more complicated solution you come up with.  (All solutions will be dominated by the O(n choose n/2).)  Very few interview candidates will respond with something like:</p>

<blockquote>
  <p>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."</p>
</blockquote>

<p>And you can use that to stand out.</p>

python recursion sub-array