# Sum of Tupleby 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) {
}
}//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) {