+ 1

Problem with return value in recursion.

This program is to count sum of elements of an array that meets the target value, using recursion. The last count value won't get added to previous count value. https://code.sololearn.com/cFkh5POV5O4S/?ref=app

22nd Feb 2022, 3:05 PM
Ajith
Ajith - avatar
11 Answers
+ 1
# does this fullfill the challenge : does_it = lambda x,y,target=11: True if x+y==11 else False from itertools import product from random import sample #lili = sample(range(20),20) lili = [3,4,7,7] lolo = list(product(lili,lili)) lala = [(i,j) for i,j in lolo if does_it(i,j,11)] result = len(lala) print(lala) print(result) # i am not using recursion # as this is more obvious
22nd Feb 2022, 4:33 PM
Ervis Meta
Ervis Meta - avatar
0
Thankyou Ervis Meta - SoloHelper for your code. But my approach is with recursion....!
22nd Feb 2022, 5:00 PM
Ajith
Ajith - avatar
0
# what about this ? #Possible combination---> (4,7)(4,7)(7,4)(7,4) def summ(arr,target,count=0): if target==0: return True if target<0: return False for i in range(len(arr)): rem=target-arr[i] if summ(arr[:i]+arr[i+1:],rem,count)==True: # di[target]=count count+=1 return rem print(summ([3,4,7,7],11))
22nd Feb 2022, 5:14 PM
Ervis Meta
Ervis Meta - avatar
0
No, it won't work for other conditions.. I can't return rem value bcse.. I was just trying to count possible combinations
22nd Feb 2022, 5:39 PM
Ajith
Ajith - avatar
0
# maybe this ? def summ(lili,target,count=0,res=[]): if target == 0: return True if target<0: return False for i in lili: for j in lili: if i+j == (target-count): # recursive part (‱‿‱) summ(lili,target-1,count+1,res=res.append((i,j))) return res lolo = summ([3,4,7,7],11) print(lolo)
22nd Feb 2022, 6:35 PM
Ervis Meta
Ervis Meta - avatar
0
Good one, but it checks only for 2 pair of combinations for example : [3,4,4,8] target 11 it fails in this case (3,4,4) or for more no. of combinations Is two for loop required...? The Time complexity of your code is o(n^2 * n^2) (in worst case) it can be solved in more efficient way. and you haven't used terminate conditions. (starting 2 if conditions)
23rd Feb 2022, 4:01 AM
Ajith
Ajith - avatar
0
# let's low down that damn time ! def subset_sum_iter(array, target): sign = 1 array = sorted(array) if target < 0: array = reversed(array) sign = -1 last_index = {0: [-1]} for i in range(len(array)): for s in list(last_index.keys()): new_s = s + array[i] if 0 < (new_s - target) * sign: pass # Cannot lead to target elif new_s in last_index: last_index[new_s].append(i) else: last_index[new_s] = [i] # Now yield up the answers. def recur(new_target, max_i): for i in last_index[new_target]: if i == -1: yield [] # Empty sum. elif max_i <= i: break # Not our solution. else: for answer in recur(new_target - array[i], i): answer.append(array[i]) yield answer for answer in recur(target, len(array)): yield answer
23rd Feb 2022, 4:56 AM
Ervis Meta
Ervis Meta - avatar
0
Nice 😊👍. The time complex has been reduced 🙃... but the problem with my recursion code is still pending..đŸ„Č
23rd Feb 2022, 5:05 AM
Ajith
Ajith - avatar
0
Could you please show me some more examples of your problem ?
23rd Feb 2022, 5:07 AM
Ervis Meta
Ervis Meta - avatar
0
Arr=[3,4,5] Traget=8 O/p: 2 (count val)#--->[(3,5),(5,3)]. #--->No repetition [(4,4)]❌ Arr=[3,4] Traget=8 O/p: 0 (count val)#--->[]. Arr=[3,4,7,7] Traget=11 O/p: 4 (count val)#--->[(4,7),(4,7),(7,4),(7,4)].
23rd Feb 2022, 5:11 AM
Ajith
Ajith - avatar
0
Problem with my code is, the last return value of count won't get added.. Its just returning new count value
23rd Feb 2022, 5:12 AM
Ajith
Ajith - avatar