Sum of Tuple
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#======================================================================
# 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