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

User · Answer

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)

User · Answer

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

User · Answer

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

User · Answer

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 lt list gt  if sum s   lt  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    gt  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   gt  for single value combinations AND r length list     r ln   gt  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

User · Answer

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 lt String gt  subsets   new ArrayList lt  gt         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 lt String gt  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

User · Answer

I used Dynamic Programming  amp  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 lt Entry  Integer gt  memoMap   new HashMap lt  gt              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 lt Entry  Integer gt  memoMap            int total   entry getTotal            int i   entry getI             if  total    0                  means element was equal in previous recursion             return 1           else if total  lt  0              means element was less in previous recursion i e  not equal             return 0           else if  i  lt  0                 means arr was finished previous recursion             return 0           else if  arr i   gt  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 lt Entry  Integer gt  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  amp  amp                      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

User · Answer

This my dynamical programming implementation in JS  It will return an array of arrays  each holding the subsequences summing to the provided target value    x000D   x000D  function getSummingItems a t   x000D    return a reduce  h n    gt  Object keys h  x000D                                    reduceRight  m k    gt   k n  lt   t    m  k n    m  k n    m  k n  concat m k  map sa   gt  sa concat n    x000D                                                                                          m k  map sa   gt  sa concat n   m  x000D                                                                      m  h    0        t   x000D    x000D  var arr   Array 20  fill   map    i    gt  i 1       1 2    20  x000D      tgt   42  x000D      res       x000D   x000D  console time  test    x000D  res   getSummingItems arr tgt   x000D  console timeEnd  test    x000D  console log  found  res length  subsequences summing to  tgt   x000D  console log JSON stringify res    x000D   x000D   x000D

User · Answer

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 lt 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 lt numbers length  i             sum numbers  i  numbers i   18  String valueOf numbers i

User · Answer

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  lt  numbers Length  i                  currentSum    numbers i           for  int j   Math Min sum  currentSum   j  gt   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

User · Answer

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

User · Answer

public class SumOfSubSet        public static void main String   args               TODO Auto-generated method stub          int a      1 2           int sum 0          if a length lt  0                System out println sum            else           for int i 0 i lt a length i                  sum sum a i               for int j i 1 j lt a length j                      sum sum a i  a j                                   System out println sum

User · Answer

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     gt    9    1  8    2  7    3  4  2

User · Answer

My backtracking solution  - Sort the array   then apply the backtracking   void  find int arr   int end vector lt int gt   amp v int start int target           if target  0           for int i   0 i lt v size   i                 cout lt  lt v i  lt  lt                        cout lt  lt endl             else          for int i    start i lt  end  amp  amp  target  gt   arr i  i                 v push back arr i                 find arr end v i 1 target-arr i                v pop back

User · Answer

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

User · Answer

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 lt int gt  amp  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 lt int gt  b   p           findAllSubsets dp  A  i-1  sum  b                 If given sum can be formed after including        current element      if  sum  gt   A i   amp  amp  dp i-1  sum-A i                   p push back A i             findAllSubsets dp  A  i-1  sum-A i   p

User · Answer

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 lt int   gt  allPossibleCombinatiosForNumbers   new ArrayList lt  gt             for  int i   2  i  lt  numbers length  i                  allPossibleCombinatiosForNumbers addAll getCombinationsOfNElements numbers  i                      for  int   combination   allPossibleCombinatiosForNumbers                printArray combination               printArrayIfNumbersSumExpectedValue combination  6                         private static List lt int   gt  getCombinationsOfNElements int   numbers  int n            int elementsKnown   n - 1          List lt int   gt  allCombinationsOfNElements   new ArrayList lt  gt             for  int i   0  i  lt  numbers length - elementsKnown  i                  int   combination   new int n               for  int j   0  j  lt  n  j                      combination j    numbers i   j                             allCombinationsOfNElements addAll generationCombinations combination  i   elementsKnown  numbers                      return allCombinationsOfNElements             private static List lt int   gt  generationCombinations int   knownElements  int index  int   numbers            List lt int   gt  combinations   new ArrayList lt  gt             for  int i   index  i  lt  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  lt  numbers length  i                  System out print numbers i                               private static void printArrayIfNumbersSumExpectedValue int   numbers  int expectedValue            int total   0          for  int i   0  i  lt  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 -------------------------------

User · Answer

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 lt String gt  allSubsets   new HashSet lt  gt                     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  gt   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

User · Answer

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  amp  empty   end  val    -10  1  -1  2  0  num   2   Output will be   2   2 0   -1 1 2   -1 1 2 0

[algorithm] find all subsets that sum to a particular value

javascript

C#

Output

Examples related to algorithm

Examples related to recursion

Examples related to subset