Sum of Tuple
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: Sum of Tuple
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given an integer array, 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 array,
 *     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""
 *   on problems that need it.
 *   (http://geekviewpoint.com/java/numbers/all_combinations)
 *
 ***************************************************************************/ 
 public List<List<Integer>> sumOfTuple(Integer[] A, int tuple, int sum) {
  String bits = """";
  for (int i = 0; i < A.length; i++) {
    bits += 1;
  }
  int power = Integer.parseInt(bits, 2);
  List<List<Integer>> result = new ArrayList<List<Integer>>();
  List<Integer> group = new ArrayList<Integer>();
  while (0 < power) {
    //if subset only has tuple number of elements
    if (tuple == countBits(power)) {
      bits = Integer.toString(power, 2);
      //sum up the elements
      int calc = 0;
      group.clear();
      for (int b = bits.length() - 1; b >= 0; b--) {
        if ('1' == bits.charAt(b)) {
          calc += A[A.length - 1 - (bits.length() - 1 - b)];
          group.add(A[A.length - 1 - (bits.length() - 1 - b)]);
        }
      }
      //if the calculated sum match the requirement, print
      if (calc == sum) {
        result.add(new ArrayList<Integer>(group));
      }
    }//if
    power--;
  }//while
  return result;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;
import static org.junit.Assert.*;

public class BitwiseTest {

  /**
   * Test of sumOfTriplet method, of class Bitwise.
   */
  @Test
  public void testSumOfTuple() {
    System.out.println(""sumOfTuple"");
    int tuple = 3;
    int sum = 15;
    Bitwise bits = new Bitwise();
    Integer[] A = {2, 3, 4, 5, 6, 7, 9, 15, 0, -2, -3, -4, -5, -6};
    Integer[][] exp = {{9, 4, 2}, {7, 6, 2}, {-2, 15, 2}, {7, 5, 3},
      {-3, 15, 3}, {6, 5, 4}, {-4, 15, 4}, {-5, 15, 5}, {0, 9, 6},
      {-6, 15, 6}};

    List<List<Integer>> expected = new ArrayList<List<Integer>>();
    for (Integer[] ar : exp) {
      expected.add(Arrays.asList(ar));
    }

    assertEquals(expected, bits.sumOfTuple(A, 3, 15));
  }
}