# Checking if three numbers sum to a given number

I'm working on the following interview practice problem, and got the following solution, which runs in worst case n! time (best case constant), and I'm trying to optimize it.

Can you offer any suggestions to go about this? I think it should be able to be reduced down to quadratic, if not nlogn, but I'm not entirely sure of an approach to achieve this.

/** Write a function to check if any three numbers in an array sum to a given number, X */
public class SumToNum {

public static void main(String[] args) {
int[] test = {1,8,2,3,11,4};
System.out.println(threeSumTo(test, 6)); //Returns true

}
public static boolean threeSumTo(int[] array, int x) {
for (int i : array) { items.add(i); }
return threeSumTo(items, x, 3);
}
public static boolean threeSumTo(List<Integer> items,int numRemaining, int count) {
if (numRemaining == 0) {
return true;
}
if (count == 0){
return false;
}
for (int i = 0; i < items.size(); i++) {
int curr = items.remove(i);
if (curr <= numRemaining) {
boolean result = threeSumTo(items, numRemaining - curr, count - 1);
if (result) {
return result;
}
}
}
return false;
}

}


EDIT: Ok, here's a solution based on Rafa's advice, using some more clever deduction. Basically, I'm just reducing it down to two integers that sum up to a number, and doing this for every number in the array. It looks like it works as intended, but in N2 worst case time this time.It also assumes the array is sorted, otherwise, as answered below, the problem is NP-Complete. Thanks for the help.

public static boolean threeSumTo(int[] array, int x) {
for (int i = 0; i < array.length; i++) {
boolean result = twoSumTo(array, x - array[i], i);
if (result) {
return result;
}
}
return false;
}

private static boolean twoSumTo(int[] array, int x, int low) {
int high = array.length - 1;
while (low < high) {
if (array[low] + array[high] == x) {
return true;
}
if (array[low] + array[high] > x) {
high--;
} else {
low++;
}
}
return false;
}

-
First think I would do is, check total of number from array that is less than the given number (in your above case, 6). If total number is less than 3, then return false –  Immer Allein Jan 20 at 3:30
You should take a moment and read through this question/answer set.... Finding pair of sum in sorted array –  rolfl Jan 20 at 4:08
Haha the final linear solution proposed is the exact thing I'm doing to solve the twoSum problem. –  BrandonM Jan 20 at 4:13

This is a specialised instance of the Subset sum problem, which is NP-Complete in the general case.

Of course, when working with a small subset size that is known in advance, we can significantly cut down on the running time (at worst checking C{n, k} values, where n is the number of values in the search space and k is the size of the subset we're looking for). The O(n^3) naive algorithm here is clearly much better than the O(n!) running time of your original algorithm. However, we can get this down to O(n^2 log n) pretty easily. Firstly, sort the original array:

private int[] values;

public Subset(int[] v)
{
values = Arrays.copyOf(v, v.length);
Arrays.sort(values);
}


Now, we can loop over each pair of indices in the array, and binary search for the difference between the calculated sum and the desired number:

public boolean sumsTo(int num)
{
int sum = 0;
for(int i = 0; i < values.length - 1; ++i) {
for(int j = i+1;  j < values.length; ++j) {
sum = values[i] + values[j];
if(Arrays.binarySearch(values, num - sum) > 0) {
return true;
}
}
}

return false;
}


In fact, with a bit more stuffing around, we can get this down to O(n^2). There is an approach to do so outlined here.

-

Hate to say it, but you have chosen some pretty slow data structures to use for your code....

Your input data is in an int[] array. This is a great data structure. You convert those values to a List, which is not as nice (more memory, slower because of data conversions, etc.), but, the real kicker, is that you use a LinkedList....

The LinkedList implementation has an O(n) access time... so, doing things like remove(i) and add(i, curr) require a scan of the list to find the position.

next up, I don't think your solution using recursion is the easiest, or the fastest.

In your case, there are really two strategies for this. The first strategy is to sort the data ( O(n log(n)) ) and then do some smart looping. The second is a naive approach. The naive approach is actually quite simple to understand:

for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
for (int k = j + 1; k < array.length; k++) {
if (array[i] + array[j] + array[k] == target) {
return true;
}
}
}
}

-
+1 simple and perfect solution –  Immer Allein Jan 20 at 3:46
Got up a n^2 I believe. Should be better. –  BrandonM Jan 20 at 4:01

Another trick that might help if the pool of numbers is large and rather random: partition it into two pools, one of even numbers and other of odds. If the sum is even, you will need either zero or two odds. If the sum is odd, you will need either one or three odds.

-

First, make the array constant. There is no need to change this array or use any other data structure.

You want an outer loop that does something like for (int i : array).

Inside that outer loop, have another loop like for( (int j = i + 1; j < max; j++).

These loops give you the first 2 numbers out of 3. If the first 2 numbers are greater than X then the 3 numbers can't be equal to X. To save time do an if( array[i] + array[j] <= x) { thing.

Finally you need an inner loop for the possible third numbers, like for( (int k = k + 1; k < max; k++) with a something like if( array[i] + array[j] + array[k] == x) return true; inside it.

That's about it - 3 loops and 2 if statements.

Note: I don't remember how to Java at the moment - syntax above might be wrong but you should hopefully understand it anyway. ;-)

Note 2: I don't know if it's possible for the numbers to be negative (they are int but Java doesn't support unsigned int). If it is possible then remove/ignore the if( array[i] + array[j] <= x) { part (because it'd be wrong in that case).

-
The general the concepts you describe are fine, but you should be careful about the details... with for (int i : array) your i will contain the values, not the indexes of the array, and then using for( (int j = i + 1; j < max; j++) the j value will likely be broken. –  rolfl Jan 20 at 3:37
@rolfl: Heh - I'm an assembly/C programmer. I was taught Java and messed with it a little, but never did find a good use for it and forgot most of it. –  Brendan Jan 20 at 3:40