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

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

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

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

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

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

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

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

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

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

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

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

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

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

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  quot wheel quot  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  quot rolls the wheel quot   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  quot wheel rolls quot  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  amp  amp  Math abs target - sum   lt  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  lt  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  lt  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  lt  numIterations  counter              for  let i   nextChange length - 1  i  gt   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   lt  0 000001                  Found a subset  Display the result              console log numbers filter  num  index    gt  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  amp  amp  Math Abs sum Value - Target   lt  0 000001F                                          Found a subset  Display the result                      Console WriteLine string Join  quot     quot   numbers Where  n  idx    gt  wheel idx       quot     quot    Target                       resultsCount                                    while  sum    null                stopwatch Stop                 Console WriteLine  quot -------------------------- quot                Console WriteLine   quot Processed  numbers Length  numbers in  stopwatch ElapsedMilliseconds   1000 0  seconds   resultsCount  results   Press any key to exit  quot                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

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

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

Examples related to algorithm

Examples related to recursion

Examples related to subset