find all subsets that sum to a particular value

Question

Given a set of numbers: {1, 3, 2, 5, 4, 9}, find the number of subsets that sum to a particular value (say, 9 for this example).

This is similar to subset sum problem with the slight difference that instead of checking if the set has a subset that sums to 9, we have to find the number of such subsets. I am following the solution for subset sum problem here. But and I am wondering how I can modify it to return the count of subsets.

Answer 1

def total_subsets_matching_sum(numbers, sum):     array = [1] + [0] * (sum)     for current_number in numbers:         for num in xrange(sum - current_number, -1, -1):             if array[num]:                 array[num + current_number] += array[num]     return array[sum]  assert(total_subsets_matching_sum(range(1, 10), 9)       == 8) assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4) 

Explanation

This is one of the classic problems. The idea is to find the number of possible sums with the current number. And its true that, there is exactly one way to bring sum to 0. At the beginning, we have only one number. We start from our target (variable Maximum in the solution) and subtract that number. If it is possible to get a sum of that number (array element corresponding to that number is not zero) then add it to the array element corresponding to the current number. The program would be easier to understand this way

for current_number in numbers:     for num in xrange(sum, current_number - 1, -1):         if array[num - current_number]:             array[num] += array[num - current_number] 

When the number is 1, there is only one way in which you can come up with the sum of 1 (1-1 becomes 0 and the element corresponding to 0 is 1). So the array would be like this (remember element zero will have 1)

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0] 

Now, the second number is 2. We start subtracting 2 from 9 and its not valid (since array element of 7 is zero we skip that) we keep doing this till 3. When its 3, 3 - 2 is 1 and the array element corresponding to 1 is 1 and we add it to the array element of 3. and when its 2, 2 - 2 becomes 0 and we the value corresponding to 0 to array element of 2. After this iteration the array looks like this

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0] 

We keep doing this till we process all the numbers and the array after every iteration looks like this

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0, 0, 0] [1, 1, 1, 2, 1, 1, 1, 0, 0, 0] [1, 1, 1, 2, 2, 2, 2, 2, 1, 1] [1, 1, 1, 2, 2, 3, 3, 3, 3, 3] [1, 1, 1, 2, 2, 3, 4, 4, 4, 5] [1, 1, 1, 2, 2, 3, 4, 5, 5, 6] [1, 1, 1, 2, 2, 3, 4, 5, 6, 7] [1, 1, 1, 2, 2, 3, 4, 5, 6, 8] 

After the last iteration, we would have considered all the numbers and the number of ways to get the target would be the array element corresponding to the target value. In our case, Array[9] after the last iteration is 8.

Answer 2

You may use Dynamic Programmining. Algo complexity is O(Sum * N) and use O(Sum) memory.

Here's my implementation in C#:

private static int GetmNumberOfSubsets(int[] numbers, int sum) {     int[] dp = new int[sum + 1];     dp[0] = 1;     int currentSum =0;     for (int i = 0; i < numbers.Length; i++)     {         currentSum += numbers[i];         for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)             dp[j] += dp[j - numbers[i]];     }      return dp[sum]; } 

Notes: As number of subsets may have value 2^N it easy may overflows int type.

Algo works only for positive numbers.