# Sum of Tupleby Isai Damier, Android Engineer @ Google

```#======================================================================
# Author: Isai Damier
# Title: Sum of Tuple
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Given a list of integers, find all k-tuples that sum up to s.
#   Use the power set algorithm.
#
# Sample Input:  array= [1,2,3,4,-3,-5], s= 0
# Sample Output: [[1,2,-3],[1,4,-5],[2,3,-5]]
#
# Technical Details:
#     1] loop through the power set of the list,
#     2] for each subset that contains k-tuple elements, sum up
#        the elements
#     3] if the calculation match the target sum, print the
#        subset.
#
# Note: This solution is by no means efficient. We are using a power set
#   to solve a particular problem: namely, the sums from subsets of a
#   specific size -- namely k-tuple.
#
#   Given a set of size n, a powerset is the set of all possible
#   combinations C(n,k) for all k between 0 and n (i.e. 0 <= k <= n).
#   The "Sum of Tuple" problem, even in its general form, is always
#   interested in the solution for a particular k. Therefore, a powerset
#   is a wasteful approach for solving this problem.
#
#   Use powerSet on problems that need it. Use "All Combinations"
#   or recursion-with-memoization on problems that need them.
#   (http://geekviewpoint.com/python/numbers/all_combinations)
#======================================================================
def sumOfTuple( _array, _tuple, _sum ):
arrayLength = len( _array )
bits = "1"*arrayLength
power = int( bits, 2 )
result = []
group = []
while 0 < power:
# if subset only has tuple number of elements
if _tuple == countBits( power ):
bits = bin( power )[2:]
# sum up the elements
calc = 0
del group[:]
k = arrayLength - len( bits )
for b in bits:
if '1' == b:
calc += _array[k]
group.append( _array[k] )
k += 1

# if the calculated sum matches the requirement, print
if calc == _sum:
result.append( list( group ) )

power -= 1
return result
```
```import unittest
from algorithms import bitwise as bits

class Test( unittest.TestCase ):

def testSumOfTuple( self ):
_tuple = 3
_sum = 15
A = [2, 3, 4, 5, 6, 7, 9, 15, 0, -2, -3, -4, -5, -6]

exp = [[2, 4, 9], [2, 6, 7], [2, 15, -2], [3, 5, 7],
[3, 15, -3], [4, 5, 6], [4, 15, -4], [5, 15, -5],
[6, 9, 0], [6, 15, -6]]

self.assertEquals( exp, bits.sumOfTuple( A, _tuple, _sum ) )
```