ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to Find all the subset of an array whose sum is equal to some number

if Sum = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.)

Implementation : Python

def tsum(currentSum,total,input,record,n):
 if total==sum :
   for i in range(0,n):
    if record[i]:
     print input[i]
				
    i = i+1
    for i in range(i,n):
     if record[i]:
      print input[i]
    print ""
    return 
 i=currentSum
 for i in range(i,n):
  if total+input[i]>sum :
   continue
  if i>0 and input[i]==input[i-1] and not record[i-1] : 
   continue
  record[i]=1
  tsum(i+1,total+input[i],input,record,l)
  record[i]=0

record = []
sum = 4
input = [4, 3, 2, 2, 1, 1]
l = len(input)
for i in range(0,l):
	record.append(0)
print "From the array the elements equal to 4 are:"
tsum(0,0,input,record,l)

OUTPUT:
labuser@ubuntu:~$ python tsum.py
From the array the elements equal to 4 are:
4

3
1

2
2

2
1
1

labuser@ubuntu:~$

A similar problem called Subset Sums can be found here

4 responses to “Algorithm to Find all the subset of an array whose sum is equal to some number

  1. zogash January 9, 2012 at 10:15 am

    thanks, it was helpful!

  2. bartender February 13, 2013 at 9:57 am

    For author:

    Great post and brilliant solution.

    Possible Update:

    The list has to be either sorted in ascending or descending order for the algorithm to work properly.So, you can call the sort method before calling the tsum function.

    For fellow readers:

    The list has to be either sorted in ascending or descending order for the algorithm to work properly.The reason for this is briefly mentioned below:

    Also as mentioned if 3+1 = 4 and there are two 1’s, and two 3’s etc. then also (3,1) should be printed only once.The records array keeps track of this condition by using the following line:

    if i>0 and input[i]==input[i-1] and not record[i-1] (line 17)

    But this step requires that all duplicates should occur together as in all 3’s should be at consecutive places and thereby be sorted. Try working out with this input set:

    [ 4, 1, 2, 2, 3, 2, 3, 4, 4] (put this on line 25 as input)

    Note that only place where we are allowed to have duplicates in our solution is 2+1+1 types:
    A snapshot of record array for this would look like:

    [0,0,1,0,1,0] ( based on input given in program by author on line 25)

    for i=5
    So,here “not record[i-1]” will evaluate to “not 1” = 0 i.e. false.So we goto line 19

  3. chitgoks April 17, 2013 at 4:16 am

    any chance you can convert it to a java method? or php or c# or javascript?

  4. Shashikant Dhama December 20, 2015 at 5:22 am

    Thank you, It was helpful 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: