LatentFreedom LatentFreedom - 1 year ago 132
Python Question

Find subarray that sums to given value in Python

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?

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]
if s == w:
d = True
return d, sa
d, sa = checkForWeight(a[1:],w,s,d,sa)
if d != True:
d, sa = checkForWeight(a[2:],w,s,d,sa)
return d, sa
sa = [] # i put this here because I want to erase the incorrect array
return d, sa

Answer Source

I made a recursive solution that works, hope it helps:

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

(The dynamic programming approach is better as keredson suggested)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download