CareerCup

1. initialize 3 dimentioanl array to cache the intermediate sums. arr[4][4][4]
2. start 2 nested loops and traverse through first 2 arrays, populate arr[4][4][0].
3. start 1 loop to calculate all other 2 dimensional planes. keep track of the sum for which matches the asked sum.
4. solution is done in n^2, which otherwise would have taken n^3 as brute force approach.

What if we sort the third array and then have nested loop on array 1 and array 2 and in each iteration of the inner loop do a binary search on array 3.

For example
Pick 1 from array A
Pick 2 from array B
and since sum is to be 7, check using binary search if 4 is present in the 3rd array.

Sort array C
Nested for loop on Array 1 and Array 2
In each iteration of the inner loop.. do a binary search on array C

eg.
Pick 1 from array A
Pick 2 from array B
Try to find 4 in array C using binary search

class Solution {
List<List<Integer>> threeSum(int[] a, int[] b, int[] c, int target) {
List<List<Integer>> res = new ArrayList<>();
for(int i = 0 ; i < a.length; i++) {
for(int j = 0; j < b.length; j++) {
int subSum = a[i] + b[j];
if(subSum < target) {
if(search(c, target - subSum)) {
res.add(Arrays.asList(a[i], b[j], target-subSum));
}
}
}
}
return res;
}
boolean search(int[] c, int target) {
int left = 0, right = c.length - 1;
while(left <= right) {
int mid = left + (right -left)/2;
if(c[mid] == target)
return true;
else if(c[mid] < target)
left = mid +1;
else
right = mid -1;
}
return false;
}

public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] b = {2, 3, 4};
int[] c = {1, 2, 4};
Solution test = new Solution();
System.out.println(test.threeSum(a, b, c, 7));
}
}

Put the elements of C in a hashMap.

Do a nested loop for above 2 arrays A and B and lookup the remaining value from the Hashmap of C.
Complexity: O(n2)

int main(){
int a[] = {1,2,3,3};
int b[] = {2,3,3,4};
int c[] = {1,2,2,2}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
n = a[i] + b[j] + c[k]
if(n == 7){
printf("[%d,%d,%d]",a[i],b[j],c[k])
}
}
}
}
}

A = [1, 2, 3, 3] 
B = [2, 3, 3, 4] 
C = [1, 2, 2, 2] 
target = 7 

def construct_candidates(constructed_sofar):
    global A,B,C
    array = A
    if 1 == len(constructed_sofar) :
        array = B
    elif 2 == len(constructed_sofar) :
        array = C
    return array
        

def over(constructed_sofar):
    global target
    sum = 0
    to_stop, reached_target = False, False
    for elem in constructed_sofar:
        sum += elem
    if sum >= target or len(constructed_sofar) >= 3 :
        to_stop = True
        if sum == target and 3 == len(constructed_sofar):
            reached_target = True
            
    return to_stop, reached_target

def backtrack(constructed_sofar):
    to_stop, reached_target = over(constructed_sofar)
    if to_stop:
        if reached_target :
            print constructed_sofar
        return
    candidates = construct_candidates(constructed_sofar)
    for candidate in candidates :
        constructed_sofar.append(candidate)
        backtrack(constructed_sofar[:])
        constructed_sofar.pop()
backtrack([])

/* 
A = [1, 2, 3, 3] 
B = [2, 3, 3, 4] 
C = [1, 2, 2, 2] 
target = 7 
*/ 
function getCombinations(a, b, c) {
  var size = a.length;
  var tuples = [];

  for (var i = 0; i < size; i++) {
    if (i >= 0 && a[i - 1] === a[i]) {
      continue;
    }

    for (var j = 0; j < size; j++) {
      if (j >= 0 && b[j - 1] === b[j]) {
        continue;
      }

      tuples.push([a[i], b[j]]);
    }
  }

  for (var k = 0, kk = tuples.length; k < kk; k++) {
    var tuple = tuples[k];
    var difference = 7 - tuple[0] - tuple[1];

    if (c.indexOf(difference) >= 0) {
      tuples[k].push(difference)
    } else {
      tuples[k] = null;
    }
  }

  return tuples;
}

Complexity: O(n(m+p))

1. Sort all the arrays - a,b,c. - This will improve average time complexity.
2. If c[i] < Sum, then look for Sum - c[i] in array a and b. When pair found, insert c[i], a[j] & b[k] into the result list. This can be done in O(n).
3. Keep on doing the above procedure while going through complete c array.

import itertools
from functools import partial
A = [1,2,3,3]
B = [2,3,3,4]
C = [1,2,2,2]
S = 7

def check_sum(N, *nums):
    if sum(x for x in nums) == N:
        return (True, nums)
    else:
        return (False, nums)

pro = itertools.product(A,B,C)
func = partial(check_sum, S)
sums = list(itertools.starmap(func, pro))

res = set()
for s in sums:
    if s[0] == True and s[1] not in res:
        res.add(s[1])
print res

import itertools
from functools import partial
A = [1,2,3,3]
B = [2,3,3,4]
C = [1,2,2,2]
S = 7

def check_sum(N, *nums):
    if sum(x for x in nums) == N:
        return (True, nums)
    else:
        return (False, nums)

pro = itertools.product(A,B,C)
func = partial(check_sum, S)
sums = list(itertools.starmap(func, pro))

res = set()
for s in sums:
    if s[0] == True and s[1] not in res:
        res.add(s[1])
print res

This is a fairly simple question.

std::set s1{1, 2, 3, 3}
std::set s2{2, 3, 3, 4}
std::set s3{1, 2, 2, 2}

for (auto & e_1: s1)
for (auto & e_2: s2)
if (s3.count(target - (e_1 + s2))) {
cout << e_1 << ", " << e_2 << ", " << target _ (e_1 + e_2) << endl;
}