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

import java.util.*;

public class MyClass {
    public static boolean[][] dp;

    static void display(List < Integer > v) {
        System.out.println(v);
    }

    // A recursive function to print all subsets with the
    // help of dp[][]. Vector p[] stores current subset.
    static void printSubsetsRec(int arr[], int i, int sum,
        ArrayList < Integer > p) {

        // If sum becomes 0
        if (sum == 0) {
            display(p);
            p.clear();
            return;
        }

        // If given sum can be achieved after ignoring
        // current element.
        if (dp[i - 1][sum]) {
            // Create a new vector to store path
            ArrayList < Integer > b = new ArrayList < > ();
            b.addAll(p);
            printSubsetsRec(arr, i - 1, sum, b);
        }

        // If given sum can be achieved after considering
        // current element.
        if (sum >= arr[i - 1] && dp[i - 1][sum - arr[i - 1]]) {
            p.add(arr[i - 1]);
            printSubsetsRec(arr, i - 1, sum - arr[i - 1], p);
        }
    }



    public static void printAllSubsets(int arr[], int N, int sum) {
        // Your code goes here
        dp = new boolean[N + 1][sum + 1];

        for (int i = 0; i <= N; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= sum; i++) {
            dp[0][i] = false;
        }



        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }


        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= sum; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }


        if (dp[N][sum] == false) {
            return;
        }

        ArrayList < Integer > p = new ArrayList < > ();
        printSubsetsRec(arr, N, sum, p);


    }
    public static void main(String args[]) {
        //  int arr[] = {1, 2, 3, 4, 5};
        int arr[] = {
            2,
            3,
            5,
            6,
            8,
            10
        };

        int n = arr.length;
        int sum = 10;
        printAllSubsets(arr, n, sum);

    }
}

Answer 2

Here is an efficient solution when there is a large set of inputs (i.e. 25 to 30)

I made efficiency gains in two ways:

• Utilized a simple rolling wheel concept for binary counting through all possible iterations, rather than using mathematically expensive base conversion language features. This "wheel" is akin to an old mechanical counter or odometer. It recursively rolls forward as many positions as necessary until we surpass the number of binary digits we have (e.g., the count of numbers in our set).
• The main gain is from not summing the entire candidate set each time. Instead, it maintains a running sum and each time it "rolls the wheel", it adjusts the running sum only for the pieces that changed from the last candidate set it tested. This saves a lot of computation since most "wheel rolls" only change a number or two.

This solution works with negative numbers, decimal amounts, and repeated input values. Due to the wonky way that floating point decimal math works in most languages, you will want to keep your input set to only a few decimal places or you may have some unpredictable behavior.

On my old 2012-era desktop computer the given code processes 25 input values in about 0.8 seconds in javascript/node.js, and 3.4 seconds in C#.

javascript

let numbers = [-0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 0.59, 0.63, 0.79, 0.85, 
0.91, 0.99, 1.02, 1.17, 1.25, 1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31];

let target = 24.16;

displaySubsetsThatSumTo(target, numbers);

function displaySubsetsThatSumTo(target, numbers)
{
    let wheel = [0];
    let resultsCount = 0;
    let sum = 0;
    
    const start = new Date();
    do {
        sum = incrementWheel(0, sum, numbers, wheel);
        //Use subtraction comparison due to javascript float imprecision
        if (sum != null && Math.abs(target - sum) < 0.000001) {
            //Found a subset. Display the result.
            console.log(numbers.filter(function(num, index) {
                return wheel[index] === 1;
            }).join(' + ') + ' = ' + target);
            resultsCount++;
        }
    } while (sum != null);
    const end = new Date();
    
    console.log('--------------------------');
    console.log(`Processed ${numbers.length} numbers in ${(end - start) / 1000} seconds (${resultsCount} results)`);
}

function incrementWheel(position, sum, numbers, wheel) {
    if (position === numbers.length || sum === null) {
        return null;
    }
    wheel[position]++;
    if (wheel[position] === 2) {
        wheel[position] = 0;
        sum -= numbers[position];
        if (wheel.length < position + 2) {
            wheel.push(0);
        }
        sum = incrementWheel(position + 1, sum, numbers, wheel);
    }
    else {
        sum += numbers[position];
    }
    return sum;
}

-----------------------------------------------------------------
Alternate, more efficient version using Gray Code binary counting
technique as suggested in comment
-----------------------------------------------------------------

const numbers = [-0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 
    0.59, 0.63, 0.79, 0.85, 0.91, 0.99, 1.02, 1.17, 1.25,
     1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31];
const target = 24.16;

displaySubsetsThatSumTo(target, numbers);

function displaySubsetsThatSumTo(target, numbers)
{
    let resultsCount = 0;
    let sum = 0;
    let wheel = []; //binary counter
    let changeEvery = []; //how often each binary digit flips
    let nextChange = []; //when each binary digit will next flip
    for(let i = 0; i < numbers.length; i++) {
        //Initialize wheel and wheel-update data. Using Gray Code binary counting technique,
        //    whereby only one binary digit in the wheel changes on each iteration. Then only
        //    a single sum operation is required each iteration.
        wheel.push(0);
        changeEvery.push(2 ** (numbers.length - i));
        nextChange.push(2 ** (numbers.length - i - 1));
    }
   
    const start = new Date();

    const numIterations = 2 ** numbers.length;
    for (counter = 1; counter < numIterations; counter++) {
        for (let i = nextChange.length - 1; i >= 0; i--) {
            if(nextChange[i] === counter) {
                nextChange[i] += changeEvery[i];
                if (wheel[i] === 1) {
                    wheel[i] = 0;
                    sum -= numbers[i];
                }
                else {
                    wheel[i] = 1;
                    sum += numbers[i];
                }
                
                break;
            }
        }

        //Use subtraction comparison due to javascript float imprecision
        if (Math.abs(target - sum) < 0.000001) {
            //Found a subset. Display the result.
            console.log(numbers.filter((num, index) => wheel[index] === 1)
                .join(' + ') + ' = ' + target);
            resultsCount++;
        }
    }

    const end = new Date();
    
    console.log('--------------------------');
    console.log(`Processed ${numbers.length} numbers in ${(end - start) / 1000} seconds (${resultsCount} results)`);
}

C#

    public class Program
    {
        static void Main(string[] args)
        {
            double[] numbers = { -0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 0.59, 0.63, 0.79, 0.85,
                0.91, 0.99, 1.02, 1.17, 1.25, 1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31 };

            double target = 24.16;

            DisplaySubsetsThatSumTo(target, numbers);
        }

        private static void DisplaySubsetsThatSumTo(double Target, double[] numbers)
        {
            var stopwatch = new System.Diagnostics.Stopwatch();

            bool[] wheel = new bool[numbers.Length];
            int resultsCount = 0;
            double? sum = 0;

            stopwatch.Start();

            do
            {
                sum = IncrementWheel(0, sum, numbers, wheel);
                //Use subtraction comparison due to double type imprecision
                if (sum.HasValue && Math.Abs(sum.Value - Target) < 0.000001F)
                {
                    //Found a subset. Display the result.
                    Console.WriteLine(string.Join(" + ", numbers.Where((n, idx) => wheel[idx])) + " = " + Target);
                    resultsCount++;
                }
            } while (sum != null);

            stopwatch.Stop();

            Console.WriteLine("--------------------------");
            Console.WriteLine($"Processed {numbers.Length} numbers in {stopwatch.ElapsedMilliseconds / 1000.0} seconds ({resultsCount} results). Press any key to exit.");
            Console.ReadKey();
        }

        private static double? IncrementWheel(int Position, double? Sum, double[] numbers, bool[] wheel)
        {
            if (Position == numbers.Length || !Sum.HasValue)
            {
                return null;
            }
            wheel[Position] = !wheel[Position];
            if (!wheel[Position])
            {
                Sum -= numbers[Position];
                Sum = IncrementWheel(Position + 1, Sum, numbers, wheel);
            }
            else
            {
                Sum += numbers[Position];
            }
            return Sum;
        }
    }

Output

-0.35 + 0.23 + 0.36 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
0.23 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.47 + 0.23 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.19 + 0.36 + 0.51 + 0.59 + 0.63 + 0.79 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.47 + -0.19 + 0.36 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
0.23 + 0.47 + 0.51 + 0.63 + 0.85 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
--------------------------
Processed 25 numbers in 0.823 seconds (6 results)

Answer 3

Python function subset that return subset of list that adds up to a particular value

def subset(ln, tar):#ln=Lenght Of String, tar= Target
s=[ int(input('Insert Numeric Value Into List:')) for i in range(ln) ]#Inserting int Values in s of type<list>
if sum(s) < tar:#Sum of List is less than Target Value
    return
elif sum(s) == tar:#Sum of list is equal to Target Value i.e for all values combinations
    return s
elif tar in s:#Target value present in List i.e for single value
    return s[s.index(tar)]
else:#For remaining possibilities i.e for all except( single and all values combinations )
    from itertools import combinations# To check all combinations ==> itertools.combinations(list,r) OR return list of all subsets of length r
    r=[i+1 for i in range(1,ln-1)]# Taking r as only remaining value combinations, i.e. 
                                 # Except(  r=1 => for single value combinations AND r=length(list) || r=ln => For all value combinations
    lst=list()#For Storing all remaining combinations
    for i in range(len(r)):
        lst.extend(list( combinations(s,r[i]) ))
    for i in range(len(lst)):# To check remaining possibilities
        if tar == sum(lst[i]):
            return list(lst[i])

subset( int(input('Length of list:')), int(input('Target:')))

Answer 4

I have found that so many interviews are asking for this so I implemented a really quite simple and understandable solution. First I generate all the possible combinations, and from there, you can do whatever you want. Check this out:

public static void main(String[] args) {
        int[] numbers = new int[]{1, 2, 3, 4, 5};
        List<int[]> allPossibleCombinatiosForNumbers = new ArrayList<>();
        for (int i = 2; i < numbers.length; i++) {
            allPossibleCombinatiosForNumbers.addAll(getCombinationsOfNElements(numbers, i));
        }
        for (int[] combination : allPossibleCombinatiosForNumbers) {
            printArray(combination);
            printArrayIfNumbersSumExpectedValue(combination, 6);
        }
    }


    private static List<int[]> getCombinationsOfNElements(int[] numbers, int n) {
        int elementsKnown = n - 1;
        List<int[]> allCombinationsOfNElements = new ArrayList<>();
        for (int i = 0; i < numbers.length - elementsKnown; i++) {
            int[] combination = new int[n];
            for (int j = 0; j < n; j++) {
                combination[j] = numbers[i + j];
            }
            allCombinationsOfNElements.addAll(generationCombinations(combination, i + elementsKnown, numbers));
        }
        return allCombinationsOfNElements;
    }

    private static List<int[]> generationCombinations(int[] knownElements, int index, int[] numbers) {
        List<int[]> combinations = new ArrayList<>();
        for (int i = index; i < numbers.length; i++) {
            int[] combinationComplete = Arrays.copyOf(knownElements, knownElements.length);
            combinationComplete[knownElements.length - 1] = numbers[i];
            combinations.add(combinationComplete);
        }
        return combinations;
    }

    private static void printArray(int[] numbers) {
        System.out.println();
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
    }

    private static void printArrayIfNumbersSumExpectedValue(int[] numbers, int expectedValue) {
        int total = 0;
        for (int i = 0; i < numbers.length; i++) {
            total += numbers[i];
        }
        if (total == expectedValue) {
            System.out.print("\n ----- Here is a combination you are looking for -----");
            printArray(numbers);
            System.out.print("\n -------------------------------");
        }
    }

Answer 5

I used Dynamic Programming & Memoization to find count of subsets from a set having a particular total. The code below code is in java. Have included the comments to explain the code intentions -

package com.company.dynamicProgramming;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class FindSumInSubSet {

    public static void main(String...args){

        int[] arr = {3, 2, 4, 6, 10};
        int total = 16;
        // Challenge is to find the subsets of numbers total 6 in above super set (represented as array)
        // In general - Write a code to count subset of elements totalling m(6 above) in given set of n(9 as array size above) elements

        Map<Entry, Integer> memoMap = new HashMap<>();

        Entry entry = new Entry(total, arr.length-1);

        int count = countSubSetForSum(arr, entry, memoMap);
        System.out.format("In set of %d elements, the number of subsets having total=%d is %d %n", arr.length,total, count);
    }


    static int countSubSetForSum(int[] arr, Entry entry, Map<Entry, Integer> memoMap){

        int total = entry.getTotal();
        int i = entry.getI();

        if (total == 0){             // means element was equal in previous recursion
            return 1;
        }else if(total < 0){         // means element was less in previous recursion i.e. not equal
            return 0;
        }else if (i < 0){            // means arr was finished previous recursion
            return 0;
        }else if (arr[i] > total){   // means element is greater than total
                                     // i.e. leave that element and look further sets excluding this element
            return getCountForIthAndTotal(arr, new Entry( total, i-1), memoMap);

        }else{                       // means element is less than total i.e. 2 possibilities :
                                     // 1st - look further sets including this element
                                     // 2nd - look further sets excluding this element
            return getCountForIthAndTotal(arr, new Entry( total-arr[i], i-1), memoMap) +
                    getCountForIthAndTotal(arr, new Entry( total, i-1), memoMap);
        }
    }


    static int getCountForIthAndTotal(int[] arr, Entry entry, Map<Entry, Integer> memoMap){
        if (memoMap.containsKey(entry)){     //look up in has table if we already calculated particular total for ith subset..
            return memoMap.get(entry);       //This is nothing but using memoization that reduce the entire below code i.e. further recursion -
        }else {
            int count = countSubSetForSum(arr, entry, memoMap);  //Recursion
            memoMap.put(entry, count); //Build memoization
            return count;
        }
    }


    //Just Data Structure for Key in HashMap (memoMaP)... intent to include particular total for ith element's subset.
    static class Entry {
        int total;
        int i;

        public Entry(int total, int i) {
            this.total = total;
            this.i = i;
        }

        public int getTotal() {
            return total;
        }

        public int getI() {
            return i;
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Entry entry = (Entry) o;
            return total == entry.total &&
                    i == entry.i;
        }

        @Override
        public int hashCode() {
            return Objects.hash(total, i);
        }
    }

}

When i ran this the out put is :

In set of 5 elements, the number of subsets having total=16 is 2 
Process finished with exit code 0

Answer 6

This my program in ruby . It will return arrays, each holding the subsequences summing to the provided target value.

array = [1, 3, 4, 2, 7, 8, 9]

0..array.size.times.each do |i| 
  array.combination(i).to_a.each { |a| print a if a.inject(:+) == 9} 
end

Answer 7

Following solution also provide array of subset which provide specific sum (here sum = 9)

array = [1, 3, 4, 2, 7, 8, 9]

(0..array.size).map { |i| array.combination(i).to_a.select { |a| a.sum == 9 } }.flatten(1)

return array of subsets which return sum of 9

 => [[9], [1, 8], [2, 7], [3, 4, 2]] 

Answer 8

Subset sum problem can be solved in O(sum*n) using dynamic programming. Optimal substructure for subset sum is as follows:

SubsetSum(A, n, sum) = SubsetSum(A, n-1, sum) || SubsetSum(A, n-1, sum-set[n-1])

SubsetSum(A, n, sum) = 0, if sum > 0 and n == 0 SubsetSum(A, n, sum) = 1, if sum == 0

Here A is array of elements, n is the number of elements of array A and sum is the sum of elements in the subset.

Using this dp, you can solve for the number of subsets for the sum.

For getting subset elements, we can use following algorithm:

After filling dp[n][sum] by calling SubsetSum(A, n, sum), we recursively traverse it from dp[n][sum]. For cell being traversed, we store path before reaching it and consider two possibilities for the element.

1) Element is included in current path.

2) Element is not included in current path.

Whenever sum becomes 0, we stop the recursive calls and print current path.

void findAllSubsets(int dp[], int A[], int i, int sum, vector<int>& p) { 

   if (sum == 0) { 
        print(p); 
        return; 
   } 

   // If sum can be formed without including current element
   if (dp[i-1][sum]) 
   { 
        // Create a new vector to store new subset 
        vector<int> b = p; 
        findAllSubsets(dp, A, i-1, sum, b); 
   } 

   // If given sum can be formed after including 
   // current element. 
   if (sum >= A[i] && dp[i-1][sum-A[i]]) 
   { 
        p.push_back(A[i]); 
        findAllSubsets(dp, A, i-1, sum-A[i], p); 
   } 

} 

Answer 9

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

Answer 10

While it is straightforward to find if their is a subset or not that sums to the target, implementation gets tricky when you need to keep track of the partial subsets under consideration.

If you use a linked list, a hash set or any another generic collection, you would be tempted to add an item to this collection before the call that includes the item, and then remove it before the call that excludes the item. This does not work as expected, as the stack frames in which the add will occur is not the same as the one in which remove will occur.

Solution is to use a string to keep track of the sequence. Appends to the string can be done inline in the function call; thereby maintaining the same stack frame and your answer would then conform beautifully to the original hasSubSetSum recursive structure.

import java.util.ArrayList;

public class Solution {

public static boolean hasSubSet(int [] A, int target) {
    ArrayList<String> subsets = new ArrayList<>();
    helper(A, target, 0, 0, subsets, "");
    // Printing the contents of subsets is straightforward
    return !subsets.isEmpty();
}

private static void helper(int[] A, int target, int sumSoFar, int i, ArrayList<String> subsets, String curr) {
    if(i == A.length) {
        if(sumSoFar == target) {
            subsets.add(curr);
        }
        return;
    }
    helper(A, target, sumSoFar, i+1, subsets, curr);
    helper(A, target, sumSoFar + A[i], i+1, subsets, curr + A[i]);
}

public static void main(String [] args) {
    System.out.println(hasSubSet(new int[] {1,2,4,5,6}, 8));
}

}

Answer 11

My backtracking solution :- Sort the array , then apply the backtracking.

void _find(int arr[],int end,vector<int> &v,int start,int target){
        if(target==0){
        for(int i = 0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }

    else{
        for(int i =  start;i<=end && target >= arr[i];i++){
            v.push_back(arr[i]);
            _find(arr,end,v,i+1,target-arr[i]);
            v.pop_back();
        }
    }
}

Answer 12

RUBY

This code will reject the empty arrays and returns the proper array with values.

def find_sequence(val, num)
  b = val.length
  (0..b - 1).map {|n| val.uniq.combination(n).each.find_all {|value| value.reduce(:+) == num}}.reject(&:empty?)
end

val = [-10, 1, -1, 2, 0]
num = 2

Output will be [[2],[2,0],[-1,1,2],[-1,1,2,0]]

Answer 13

public class SumOfSubSet {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int a[] = {1,2};
        int sum=0;
        if(a.length<=0) {
            System.out.println(sum);
        }else {
        for(int i=0;i<a.length;i++) {
            sum=sum+a[i];
            for(int j=i+1;j<a.length;j++) {
                sum=sum+a[i]+a[j];
            }
        }
        System.out.println(sum);

        }


    }

}

Answer 14

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.

Answer 15

I have solved this by java. This solution is quite simple.

import java.util.*;

public class Recursion {

static void sum(int[] arr, int i, int sum, int target, String s)
{   
    for(int j = i+1; j<arr.length; j++){
        if(sum+arr[j] == target){
            System.out.println(s+" "+String.valueOf(arr[j]));
        }else{
            sum(arr, j, sum+arr[j], target, s+" "+String.valueOf(arr[j]));
        }
    }
}

public static void main(String[] args)
{   
    int[] numbers = {6,3,8,10,1};
    for(int i =0; i<numbers.length; i++){
        sum(numbers, i, numbers[i], 18, String.valueOf(numbers[i])); 
    }

}
}

Answer 16

This my dynamical programming implementation in JS. It will return an array of arrays, each holding the subsequences summing to the provided target value.

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
    tgt = 42,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));

Answer 17

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 18

The usual DP solution is true for the problem.

One optimization you may do, is to keep a count of how many solutions exist for the particular sum rather than the actual sets that make up that sum...

Answer 19

The same site geeksforgeeks also discusses the solution to output all subsets that sum to a particular value: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/

In your case, instead of the output sets, you just need to count them. Be sure to check the optimized version in the same page, as it is an NP-complete problem.

This question also has been asked and answered before in stackoverflow without mentioning that it's a subset-sum problem: Finding all possible combinations of numbers to reach a given sum