find all subsets that sum to a particular value

Solution 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.

Solution 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.

Solution 3:

Here is a Java Solution:

This is a classical Back tracking problem for finding all possible subsets of the integer array or set that is the input and then filtering those which sum to e given target

import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * Created by anirudh on 12/5/15.
 */
public class findSubsetsThatSumToATarget {

    /**
     * The collection for storing the unique sets that sum to a target.
     */
    private static HashSet<String> allSubsets = new HashSet<>();

    /**
     * The String token
     */
    private static final String token = " ";

    /**
     * The method for finding the subsets that sum to a target.
     *
     * @param input  The input array to be processed for subset with particular sum
     * @param target The target sum we are looking for
     * @param ramp   The Temporary String to be beefed up during recursive iterations(By default value an empty String)
     * @param index  The index used to traverse the array during recursive calls
     */
    public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) {

        if(index > (input.length - 1)) {
            if(getSum(ramp) == target) {
                allSubsets.add(ramp);
            }
            return;
        }

        //First recursive call going ahead selecting the int at the currenct index value
        findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1);
        //Second recursive call going ahead WITHOUT selecting the int at the currenct index value
        findTargetSumSubsets(input, target, ramp, index + 1);
    }

    /**
     * A helper Method for calculating the sum from a string of integers
     *
     * @param intString the string subset
     * @return the sum of the string subset
     */
    private static int getSum(String intString) {
        int sum = 0;
        StringTokenizer sTokens = new StringTokenizer(intString, token);
        while (sTokens.hasMoreElements()) {
            sum += Integer.parseInt((String) sTokens.nextElement());
        }
        return sum;
    }

    /**
     * Cracking it down here : )
     *
     * @param args command line arguments.
     */
    public static void main(String[] args) {
        int [] n =  {24, 1, 15, 3, 4, 15, 3};
        int counter = 1;
        FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0);
        for (String str: allSubsets) {
            System.out.println(counter + ") " + str);
            counter++;
        }
    }
}

It gives space separated values of the subsets that sum to a target.

Would print out commma separated values for the subsets that sum to 25 in {24, 1, 15, 3, 4, 15, 3}

1) 24 1

2) 3 4 15 3

3) 15 3 4 3