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>I made a recursive solution that works, hope it helps:</p>

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

<p>(The dynamic programming approach is better as keredson suggested)</p>

python recursion sub-array