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) {
      List&lt;Integer&gt; items = new LinkedList&lt;&gt;();
      for (int i : array) { items.add(i); }
      return threeSumTo(items, x, 3);
  }
  public static boolean threeSumTo(List&lt;Integer&gt; items,int numRemaining, int count) {
      if (numRemaining == 0) { 
          return true; 
      }
      if (count == 0){ 
          return false; 
      }
      for (int i = 0; i &lt; items.size(); i++) {
          int curr = items.remove(i);
          if (curr &lt;= numRemaining) {
              boolean result = threeSumTo(items, numRemaining - curr, count - 1);
              if (result) {
                  return result;
              }
          }
          items.add(i, curr);
      }
      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 &lt; 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 &lt; high) {
        if (array[low] + array[high] == x) {
            return true;
        }
        if (array[low] + array[high] &gt; x) {
            high--;
        } else {
            low++;
        }
    }
    return false;
}
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 &lt; values.length - 1; ++i) { 
        for(int j = i+1;  j &lt; values.length; ++j) {
            sum = values[i] + values[j];
            if(Arrays.binarySearch(values, num - sum) &gt; 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.