Sum of Tuple
by Isai Damier

#======================================================================
# 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 ) )