Find all subsets of a set that sum up to n

Viewed 1964

Here is the code that I came up with:

static void findNumbers(int[] list, int index, int current, int goal, String result)
{ 
  if (list.length < index || current>goal)
          return;
   for (int i = index; i < list.length; i++) {
      if (current + list[i] == goal)   {
         System.out.println(result + " " + String.valueOf(list[i]));
       }
       else if (current + list[i] < goal) {
           findNumbers(list, i + 1, current + list[i], goal, result + " " + String.valueOf(list[i]));
        }
   }
}

Call it using:

findNumbers(array, starting_index, current_sum_till_now, target_sum, "");

Can someone help me figure out the time complexity of this code I believe its exponential.

What is the most optimal way to solve this problem? Is it using backtrack?

4 Answers
Related