# FB Phone - Tuple Combination Sum

• Q: Write a function that list any 3 elements that sum to zero, from an array of integers.

Notes:

1. We need all unique solutions. (-5, -5, 10) is same as (10, -5, -5)
2. The same element can be used multiple times.

Example
Input: [-5, 1, 10, 2, 3] // array of integers
Output: [(-5, -5, 10), (-5, 2, 3)] // array of tuples

• I know this is similar to this problem - https://leetcode.com/problems/combination-sum/#/description. But the challenging thing is the array can contain negative elements. Any idea how we can solve this.

1. also similar to 3 sum

2. for backtrace
Helper(List<List<int>> res, List<int> temp, int[] arr, int index, int sum, int count){
if(index>=arr.Length)
return;
if(count==0){
if(sum==0) // meet condition
return;
}

Helper(.....index+1,...)// do nothing. go to next index, choose 0 time
for(int i=1；i<=count;i++){// choose current item, choose 1 time, choose 2 time, choose 3 time
sum+=arr[index];
Helper(....index+1,sum,count-i);
}

//remove all arr[index] from temp.
for(int i=1;i<=count;i++){
temp.remove(arr[index]);
}
}

• @skong03 Thanks for your code. I tried to solve this similar to 3sum. I copied each element in the array thrice (since we are looking for tuples) and built the new expanded input array. Then sorted the elements to skip the duplicate elements.

• ``````
def threesumzero(a):
"""
Find triplets that sum to zero
:param a: an array of integers to analyze
:return: return unique triplets out of input array that sum to zero, an item in triplet may repeat at most twice
"""
result = set()  # set to eliminate deuplicates!
a.sort() # sort it
n = len(a) # number of items in a
for x in a: # for each element in a, see if its part of some triplet
target_sum = 0 - x # x and other two items must sum to 0, so other two must sum to -x
i = 0 # from beginning
j = n - 1 # from end
while i < j:
if a[i] + a[j] == target_sum: # we found triplet
result.add( tuple( sorted( [x, a[i], a[j] ] ) ) ) # sort it (for uniqueness) and convert it to tuple as its immutable
i += 1
j -= 1
elif a[i] + a[j] > target_sum:
j -= 1
else: # a[i] + a[j] < target_sum
i += 1

return result``````

• ``````public class Solution11 {
public Solution11() {
super();
}
static Set<List> set = new HashSet<List>();
public static void main(String[] args){
int[] arr = {-5,1,10,2,3};
for(int i=0;i<arr.length;i++){
findSet(arr,i);
}
System.out.println(set.toString());
}

public static void findSet(int[] arr, int i){
for(int j=0;j<arr.length;j++){
List<Integer> list = new ArrayList<Integer>();
int output = findSet2(arr,i,j,list, arr[i]+arr[j]);
if(output != 0){
Collections.sort(list);
}
}
}

public static int findSet2(int[] arr, int i, int j, List<Integer> list,int sum){
return (j == arr.length) ? 0 : ((sum + arr[j] == 0) ? arr[j] : findSet2(arr,i,j+1,list,sum));
}
}``````

• Simple but slow Python solution ( O(N^3))

``````def find_triplets(a):
solutions = set()
if len(a) < 3:
return 0
for x in range(len(a)-2):
for y in range(x, len(a)-1):
for z in range(y, len(a)):
if a[x] + a[y] + a[z] == 0:
return list(solutions)

print(find_triplets([-5, 1, 10, 2, 3]))
``````

• Assume input array doesn't have duplicate number. If it has, remove first.

``````    public static void main(String[] args) {
int[] nums = new int[]{-5, 1, 10, 2, 3, 7, 8, -11, 11, -6};
System.out.println(tupleSum(nums));
}
private static List<List<Integer>> tupleSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int l = i, r = nums.length - 1;
while (l <= r) {
if (nums[i] + nums[l] + nums[r] > 0) {
r--;
} else if (nums[i] + nums[l] + nums[r] < 0) {
l++;
} else {
l++;
r--;
}
}
}
return res;
}
``````

• This question is very similar to the combination sum. just do not need to sort and return when the number of the current list reaches 3.

``````class Solution {
public:
void helper(const vector<int>& curr_list, int target,
const vector<int>& candidates, int start_index,
vector<vector<int>>* res) {
if (curr_list.size() == 3) {
if (target == 0) {
res->push_back(curr_list);
}
return;
}

for (int i = start_index; i < candidates.size(); i++) {
int diff = target - candidates[i];
auto new_vec = curr_list;
new_vec.push_back(candidates[i]);
helper(new_vec, diff, candidates, i, res);
}
}

vector<vector<int>> combinationSum(vector<int>& candidates) {
vector<vector<int>> res;
helper(vector<int>(), 0, candidates, 0, &res);
return res;
}
};
``````

• @sureshrmdec Here's my solution in python - it creates a new array with each element repeated three times and checks all possible triples.

``````def find_triples(arr):
new_arr = []
for num in arr:
new_arr.extend([num]*3)
new_arr.sort()
sol = set()
for i in range(len(new_arr)-2):
j = i+1
k = len(new_arr) - 1
while j < k:
total = new_arr[i] + new_arr[j] + new_arr[k]
if total < 0:
j += 1
elif total > 0:
k -= 1
else:
k -= 1
j += 1

return sol
``````

• Followings are all possibilities for sum of a tuple to be zeros.
(0, 0, 0)
One 0, one negative and one positive.
Two negatives and one positive. Two negatives can be the same.
Two positives and one negative. Two positives can be the same.
After sorting the array into negatives, 0, and positives, the last three cases become two sum problem at smaller scale.
This seems to be tedious. But, it will provide unique answers.
The downside is that it is not very scalable.

• void find_tuple(int* data, int len)
{
int i, j, k, sum;

``````for (i = 0; i < len; i++)
{
for (j = i; j < len; j++)
{
for (k = j; k < len; k++)
{
sum = data[i] + data[j] + data[k];
if (sum == 0)
{
printf("(%d, %d, %d)\n", data[i], data[j], data[k]);
}
}
}
}
``````

}

• Simple but slow Python solution ( O(N^3))

``````def find_triplets(a):
solutions = set()
if len(a) < 3:
return 0
for x in range(len(a)-2):
for y in range(x, len(a)-1):
for z in range(y, len(a)):
if a[x] + a[y] + a[z] == 0: