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 here.
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.
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.
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.