Find all the subsets of the set summing up to n

Question

Here is the code 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]));
        }
   }
}

Name 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 find it exponential.

What is the best way to solve this problem? Is the return path used?

Answer 1

It was indicated that I made a mistake. I multiplied the complexity of recursive calls while I had to add them. So C(N) = C(N-1) + C(N-2) + .... The same applies to C(N-1), C(N-2)etc. That means complexity isnt O(N!).

. . 2^N - 1 ( ), O(2^N), .

Answer 2

, " - , - , ". :

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);
}

O(2^n), n=>5, O(n!). , , . , 2- else if, , , list[index], , .

O(2^l), l - , , , n, .

: findNumbers(list,0,0,goal,"")

Answer 3

, , N ^ 2, O (N!). , , , .

, , , , , . , , , , , ( , , ). , , , , , .

Answer 4

, : -

• list[i] <= N

• N , , list[i]

• N = , .

• .

: O(|S|*N + K) |S|- length of set and K is number of subsets. .

: NP- .

: -

void retrace(int n,boolean[] solution,int target) {

   if(n>=0) {

        if(table[target][n-1]) {

            solution[n] = false;
            retrace(n-1,solution,target); 
        }

       if(table[target-numbers[n]][n-1]) {

            solution[n] = true;
            retrace(n-1,solution,target-numbers[n]);
       }
   }

   else {
       printf("\nsubset:-\n");
       for(int i=0;i<solution.length;i++) {

            if(solution[i]) {
                printf(number[i]+" ");
            }
       }

   }


}



  Call : - retrace(numbers.length-1,new boolean[numbers.length],target);