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

### Like this:

Like Loading...

*Related*

thanks, it was helpful!

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

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

Thank you, It was helpful 😀