Find all subsets of a set that sum up to n

Question

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?

Answer 1

Here is a way to do it using dynamic programming and knapsack analogy : -

1. Sort the set in ascending order

2. Evaluate subset till list[i] <= N

3. Solve Knapsack for sack of capacity N and items having value and weight as their list[i]

4. If at end knapsack capacity N == max profit then atleast one solution subset exists.

5. retrace all solutions for knapsack using cost matrix and get all the solution subsets.

Time complexity: O(|S|*N + K) |S|- length of set and K is number of subsets. This is a pseudo polynomial time algorithm.

Note: Problem being NP-hard no polynomial time algorithm is yet discovered.

Edit:- Retrace solution from boolean matrix

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

Answer 2

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,"")

Answer 3

As has just been pointed out it is worse than N^2, in fact it looks like O(N!). You will save a bit as you can exit on some of the loops early but the degree of saving would depend on how fast possibilities get eliminated.

In terms of a more optimal solutions you are going to struggle, this is an excellent case for recursion as any loop based construct is going to be horrific. You may be able to save some time by pre-sorting your data so larger values are first and hence you reach target faster (this will essentially eliminate anything in your list that is larger than your goal immediately). After the too-big entries are eliminated I am not sure if it will help directly as you still need to compare everything with everything but it might improve the processor branch predictions.

Answer 4

It has been pointed out that I've done a mistake. I were multiplying the complexities of recursive calls while I should have added them. So C(N) = C(N-1) + C(N-2) + .... The same would then apply to C(N-1), C(N-2), etc. This means that the complexity isnt' O(N!).

This have made me thinking on the algorithm from another point of view. It is checking every single possible subset. Since there are 2^N - 1 possible subsets (the empty subset is not taken into account), then the complexity is O(2^N), which I think is your original bet.