You can modify your code to work on the principle "if a number is good - add it; disregarding any condition skip current number". In this case the code will be:
static void findNumbers(int[] list, int index, int current, int goal, String result)
{
if (list.length <= index || current>goal) // I've added the "=" which is missing in your code.
return;
if (current + list[index] == goal) {
System.out.println(result + " " + String.valueOf(list[i]));
}
else if (current + list[index] < goal) {
findNumbers(list, index + 1, current + list[i], goal, result + " " + String.valueOf(list[i]));
}
findNumbers(list, index + 1, current, goal, result);
}
In this case the complexity will be O(2^n)
which is better for n=>5
then O(n!)
.
As it was pointed out, the complexity is reduced if the array is sorted. Meaning you can put the 2nd recursive call inside the else if
because you will be sure that all number that follow are greater then the current list[index]
meaning there is no use skipping this value because all following branches from this call will not generate any valid subsets.
In this case the worst case is O(2^l)
where l
is either the index of a number that is greater then your goal and is in your array, or n
if such a number doesn't exist.
The call should be: findNumbers(list,0,0,goal,"")