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]
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
``````

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