0

I am working on a code to identify subsets of an array with sum of the elements in subsets equal to a given number, k. Here is the recursive code I attempted.

First approach:

def subset_sum(arr,curr,k,idx):
   if idx==len(arr):
      print(curr) //print the current subset for debugging
      if sum(curr)==k:
         print(curr)
      return
   subset_sum(arr,curr,k,idx+1) //exclude the element
   curr.append(arr[idx]) //include the element
   subset_sum(arr,curr,k,idx+1) // make recursive call

Then this function has been called using;subset_sum([1,2,3],[],4,0), and we get following output;

[]
[3]
[3]
[3, 2]
[3, 2, 3]
[3, 2, 3, 1]
[3, 2, 3, 1, 3]
[3, 2, 3, 1, 3, 2]
[3, 2, 3, 1, 3, 2, 3]

It is being difficult to comprehend, why are the elements being duplicated above. After some brainstorming, I tried second approach below.

Second approach.

def subset_sum(arr,curr,k,idx):
    cnt=0
    if idx==len(arr):
   
       if sum(curr)==k:
          cnt+=1
          print(curr,cnt)
       return cnt

   subset_sum(arr,curr,k,idx+1)
   subset_sum(arr,curr+[arr[idx]],k,idx+1)

We call the function subset_sum([1,2,3],[],3,0,0). This gives the output as;

[1,2],1
[3],1

since 1+2 gives us the required sum 3. May I know what is wrong in updating the element curr as I did in the first approach; curr.append(arr[idx]). And why is that the second approach is working fine.

jay
  • 1,319
  • 6
  • 23
  • 42
  • I hope this is a school exercise and not real code in production. In python indexes are useless 90% of the time. See [this](https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements) QA – Pynchia Sep 25 '20 at 05:44
  • In the first approach you keep appending to the same list, while the second one creates a new list on every recursive call. – ggorlen Sep 25 '20 at 14:46
  • @Pynchia yes it is not a production code. Actually I am trying to learn recursion from scratch to strengthen my fundamentals. Apprecitae your reply. – jay Sep 25 '20 at 16:21
  • @ggorlen. Appreciate your explanation. makes sense. I will make sure to keep in mind this concept. One thing I wanted to know, if I want to count number of subsets with sum same as `k`, may I know what changes will be essential. – jay Sep 25 '20 at 16:23
  • Add a counter to keep track. – ggorlen Sep 25 '20 at 16:31
  • @ggorlen I did add a variable 'cnt' to my code in second approach above.But since it is getting reset each time because of recursive call, I m not getting cumulative count of subsets. Can you kindly advise on what shall I modify in the code? thanks – jay Oct 02 '20 at 03:20
  • Pass the count using `return` back up the call chain. Accumulate along the way up and when all calls resolve, the original caller is left holding the answer. In other words, don't pass `cnt` down as a parameter. – ggorlen Oct 02 '20 at 03:22
  • @ggorlen I tried to update my code without passing 'cnt' as a parameter, in my revised second approach. But it still seems to be resetting. Can I please get some help? – jay Oct 02 '20 at 04:27
  • You're only returning from the terminal nodes in the call tree--you need to pass count back up in every recursive call, so `return subset_sum(arr,curr,k,idx+1) + subset_sum(arr,curr+[arr[idx]],k,idx+1)` – ggorlen Oct 02 '20 at 04:31
  • @ggorlen Thanks for your help. it works now. Appreciate it. Is there any good easy to understand tutorial on Recursion which can dig into its nitty gritty details. Kindly share if you are aware of any. – jay Oct 04 '20 at 23:49

0 Answers0