Finding all possible combinations of numbers to reach a given sum

Question

How would you go about testing all possible combinations of additions from a given set N of numbers so they add up to a given final number   A brief example    Set of numbers to add  N    1 5 22 15 0      Desired result  12345

User · Answer

Here is a Java version which is well suited for small N and very large target sum, when complexity O(t*N) (the dynamic solution) is greater than the exponential algorithm. My version uses a meet in the middle attack, along with a little bit shifting in order to reduce the complexity from the classic naive O(n*2^n) to O(2^(n/2)).

If you want to use this for sets with between 32 and 64 elements, you should change the int which represents the current subset in the step function to a long although performance will obviously drastically decrease as the set size increases. If you want to use this for a set with odd number of elements, you should add a 0 to the set to make it even numbered.

import java.util.ArrayList;
import java.util.List;

public class SubsetSumMiddleAttack {
    static final int target = 100000000;
    static final int[] set = new int[]{ ... };

    static List<Subset> evens = new ArrayList<>();
    static List<Subset> odds = new ArrayList<>();

    static int[][] split(int[] superSet) {
        int[][] ret = new int[2][superSet.length / 2]; 

        for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];

        return ret;
    }

    static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
        accumulator.add(new Subset(subset, sum));
        if (counter != superSet.length) {
            step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
            step(superSet, accumulator, subset, sum, counter + 1);
        }
    }

    static void printSubset(Subset e, Subset o) {
        String ret = "";
        for (int i = 0; i < 32; i++) {
            if (i % 2 == 0) {
                if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
            else {
                if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
        }
        if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
        System.out.println(ret);
    }

    public static void main(String[] args) {
        int[][] superSets = split(set);

        step(superSets[0], evens, 0,0,0);
        step(superSets[1], odds, 0,0,0);

        for (Subset e : evens) {
            for (Subset o : odds) {
                if (e.sum + o.sum == target) printSubset(e, o);
            }
        }
    }
}

class Subset {
    int subset;
    int sum;

    Subset(int subset, int sum) {
        this.subset = subset;
        this.sum = sum;
    }
}

User · Answer

I thought I d use an answer from this question but I couldn t  so here is my answer  It is using a modified version of an answer in Structure and Interpretation of Computer Programs  I think this is a better recursive solution and should please the purists more   My answer is in Scala  and apologies if my Scala sucks  I ve just started learning it   The findSumCombinations craziness is to sort and unique the original list for the recursion to prevent dupes     def findSumCombinations target  Int  numbers  List Int    Int       cc target  numbers distinct sortWith    lt      List       def cc target  Int  numbers  List Int   solution  List Int    Int       if  target    0   println solution   1     else if  target  lt  0    numbers length    0  0   else      cc target  numbers tail  solution         cc target - numbers head  numbers  numbers head    solution      To use it     gt  findSumCombinations 12345  List 1 5 22 15 0         Prints a whole heap of lists that will sum to the target

User · Answer

This is similar to a coin change problem  public class CoinCount       public static void main String   args        int   coins  1 4 6 2 3 5       int count 0       for  int i 0 i lt coins length i                  count count Count 9 coins i 0             System out println count      public static int Count int Sum int   coins int index int curSum        int count 0       if  index gt  coins length          return 0       int sumNow curSum coins index       if  sumNow gt Sum          return 0      if  sumNow  Sum          return 1       for  int i  index 1 i lt coins length i            count  Count Sum coins i sumNow        return count

User · Answer

In Haskell   filter       12345   sum    subsequences  1 5 22 15 0       And J       12345     gt     lt         i 2   1 5 22 15 0       As you may notice  both take the same approach and divide the problem into two parts  generate each member of the power set  and check each member s sum to the target   There are other solutions but this is the most straightforward   Do you need help with either one  or finding a different approach

User · Answer

function solve n       let DP             DP 0    DP 1    DP 2    1       DP 3    2       for  let i   4  i  lt   n  i            DP i    DP i-1    DP i-3    DP i-4             return DP n     console log solve 5      This is a Dynamic Solution for JS to tell how many ways anyone can get the certain sum  This can be the right solution if you think about time and space complexity

User · Answer

Here s a solution in R  subset sum   function numbers target partial 0     if any is na partial    return     s   sum partial    if s    target  print sprintf  sum  s   s  paste partial -1  collapse      target     if s  gt  target  return     for  i in seq along numbers        n   numbers i      remaining   numbers  i 1  length numbers       subset sum remaining target c partial n

User · Answer

I was doing something similar for a scala assignment  Thought of posting my solution here    def countChange money  Int  coins  List Int    Int           def getCount money  Int  remainingCoins  List Int    Int             if money    0   1         else if money  lt  0    remainingCoins isEmpty  0         else           getCount money  remainingCoins tail                getCount money - remainingCoins head  remainingCoins                if money    0    coins isEmpty  0       else getCount money  coins

User · Answer

An iterative C   stack solution for a flavor of this problem  Unlike some other iterative solutions  it doesn t make unnecessary copies of intermediate sequences     Given a positive integer  return all possible combinations of    positive integers that sum up to it    vector lt vector lt int gt  gt  print all sum int target       vector lt vector lt int gt  gt  output      vector lt int gt  stack       int curr min   1      int sum   0      while  curr min  lt  target            sum    curr min          if  sum  gt   target                if  sum    target                    output push back stack      make a copy                 output back   push back curr min                             sum -  curr min   stack back                curr min   stack back     1              stack pop back              else               stack push back curr min                        return output

User · Answer

There are a lot of solutions so far  but all are of the form generate then filter   Which means that they potentially spend a lot of time working on recursive paths that do not lead to a solution  Here is a solution that is O size of array    number of sums   number of solutions     In other words it uses dynamic programming to avoid enumerating possible solutions that will never match  For giggles and grins I made this work with numbers that are both positive and negative  and made it an iterator   It will work for Python 2 3   def subset sum iter array  target       sign   1     array   sorted array      if target  lt  0          array   reversed array          sign   -1      last index    0   -1       for i in range len array            for s in list last index keys                 new s   s   array i              if 0  lt   new s - target    sign                  pass   Cannot lead to target             elif new s in last index                  last index new s  append i              else                  last index new s     i         Now yield up the answers      def recur  new target  max i           for i in last index new target               if i    -1                  yield      Empty sum              elif max i  lt   i                  break   Not our solution              else                  for answer in recur new target - array i   i                       answer append array i                       yield answer      for answer in recur target  len array            yield answer  And here is an example of it being used with an array and target where the filtering approach used in other solutions would effectively never finish  def is prime  n       for i in range 2  n           if 0    n i              return False         elif n  lt  i i              return True     if n    2          return True     else          return False  def primes  limit       n   2     while True          if is prime n               yield n          n   n 1         if limit  lt  n              break  for answer in subset sum iter primes 1000   76000       print answer   This prints all 522 answers in under 2 seconds   The previous approaches would be lucky to find any answers in the current lifetime of the universe    The full space has 2 168   3 74144419156711e 50 possible combinations to run through   That   takes a while

User · Answer

Swift 3 conversion of Java solution   by  JeremyThompson   protocol  IntType     extension Int   IntType      extension Array where Element   IntType        func subsets to  Int  - gt    Element               func sum up recursive   numbers   Element     target  Int    partial   Element     solution  inout   Element                   var sum  Int   0             for x in partial                   sum    x as  Int                            if sum    target                   solution append partial                             guard sum  lt  target else                   return                            for i in stride from  0  to  numbers count  by  1                     var remaining    Element                     for j in stride from  i   1  to  numbers count  by  1                        remaining append numbers j                                      var partial rec    Element  partial                  partial rec append numbers i                    sum up recursive remaining  target  partial rec   amp solution                                   var solutions     Element             sum up recursive self  to   Element      amp solutions           return solutions count  gt  0   solutions   nil            usage   let numbers    3  9  8  4  5  7  10   if let solution   numbers subsets to  15        print solution     output    3  8  4    3  5  7    8  7    5  10     else       print  not possible

User · Answer

C  version of  msalvadores code answer  void Main         int   numbers    3 9 8 4 5 7 10       int target   15      sum up new List lt int gt  numbers ToList    target      static void sum up recursive List lt int gt  numbers  int target  List lt int gt  part       int s   0     foreach  int x in part              s    x          if  s    target               Console WriteLine  sum     string Join      part Select n   gt  n ToString    ToArray             target           if  s  gt   target               return          for  int i   0 i  lt  numbers Count i                  var remaining   new List lt int gt              int n   numbers i            for  int j   i   1  j  lt  numbers Count j                            remaining Add numbers j                        var part rec   new List lt int gt  part            part rec Add n            sum up recursive remaining target part rec          static void sum up List lt int gt  numbers  int target        sum up recursive numbers target new List lt int gt

User · Answer

Java non-recursive version that simply keeps adding elements and redistributing them amongst possible values  0 s are ignored and works for fixed lists  what you re given is what you can play with  or a list of repeatable numbers     import java util     public class TestCombinations        public static void main String   args            ArrayList lt Integer gt  numbers   new ArrayList lt  gt  Arrays asList 0  1  2  2  5  10  20            LinkedHashSet lt Integer gt  targets   new LinkedHashSet lt Integer gt                   add 4               add 10               add 25                        System out println     each element can appear as many times as needed            for  Integer target  targets                Combinations combinations   new Combinations numbers  target  true               combinations calculateCombinations                for  String solution  combinations getCombinations                      System out println solution                                    System out println     each element can appear only once            for  Integer target  targets                Combinations combinations   new Combinations numbers  target  false               combinations calculateCombinations                for  String solution  combinations getCombinations                      System out println solution                                      public static class Combinations           private boolean allowRepetitions          private int   repetitions          private ArrayList lt Integer gt  numbers          private Integer target          private Integer sum          private boolean hasNext          private Set lt String gt  combinations                          Constructor                         param numbers Numbers that can be used to calculate the sum              param target  Target value for sum                      public Combinations ArrayList lt Integer gt  numbers  Integer target                this numbers  target  true                                     Constructor                         param numbers Numbers that can be used to calculate the sum              param target  Target value for sum                      public Combinations ArrayList lt Integer gt  numbers  Integer target  boolean allowRepetitions                this allowRepetitions   allowRepetitions              if  this allowRepetitions                    Set lt Integer gt  numbersSet   new HashSet lt  gt  numbers                   this numbers   new ArrayList lt  gt  numbersSet                 else                   this numbers   numbers                            this numbers removeAll Arrays asList 0                Collections sort this numbers                this target   target              this repetitions   new int this numbers size                 this combinations   new LinkedHashSet lt  gt                  this sum   0              if  this repetitions length  gt  0                  this hasNext   true              else                 this hasNext   false                                    Calculate and return the sum of the current combination                         return The sum                      private Integer calculateSum                 this sum   0              for  int i   0  i  lt  repetitions length    i                    this sum    repetitions i    numbers get i                             return this sum                                    Redistribute picks when only one of each number is allowed in the sum                      private void redistribute                 for  int i   1  i  lt  this repetitions length    i                    if  this repetitions i - 1   gt  1                        this repetitions i - 1    0                      this repetitions i     1                                              if  this repetitions this repetitions length - 1   gt  1                  this repetitions this repetitions length - 1    0                                    Get the sum of the next combination  When 0 is returned  there s no other combinations to check                         return The sum                      private Integer next                 if  this hasNext  amp  amp  this repetitions length  gt  0                    this repetitions 0     1                  if   this allowRepetitions                      this redistribute                    this calculateSum                     for  int i   0  i  lt  this repetitions length  amp  amp  this sum    0    i                        if  this sum  gt  this target                            this repetitions i    0                          if  i   1  lt  this repetitions length                                this repetitions i   1     1                              if   this allowRepetitions                                  this redistribute                                                      this calculateSum                                                             if  this sum compareTo 0     0                      this hasNext   false                            return this sum                                    Calculate all combinations whose sum equals target                      public void calculateCombinations                 while  this hasNext                    if  this next   compareTo target     0                      this combinations add this toString                                                     Return all combinations whose sum equals target                         return Combinations as a set of strings                      public Set lt String gt  getCombinations                 return this combinations                      Override         public String toString                 StringBuilder stringBuilder   new StringBuilder      sum                      for  int i   0  i  lt  repetitions length    i                    for  int j   0  j  lt  repetitions i     j                        stringBuilder append numbers get i                                                      return stringBuilder toString                        Sample input   numbers  0  1  2  2  5  10  20 targets  4  10  25   Sample output      each element can appear as many times as needed 4  1 1 1 1  4  1 1 2  4  2 2  10  1 1 1 1 1 1 1 1 1 1  10  1 1 1 1 1 1 1 1 2  10  1 1 1 1 1 1 2 2  10  1 1 1 1 2 2 2  10  1 1 2 2 2 2  10  2 2 2 2 2  10  1 1 1 1 1 5  10  1 1 1 2 5  10  1 2 2 5  10  5 5  10  10  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2  25  1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2  25  1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2  25  1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2  25  1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2  25  1 1 1 1 1 2 2 2 2 2 2 2 2 2 2  25  1 1 1 2 2 2 2 2 2 2 2 2 2 2  25  1 2 2 2 2 2 2 2 2 2 2 2 2  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5  25  1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5  25  1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5  25  1 1 1 1 1 1 1 1 2 2 2 2 2 2 5  25  1 1 1 1 1 1 2 2 2 2 2 2 2 5  25  1 1 1 1 2 2 2 2 2 2 2 2 5  25  1 1 2 2 2 2 2 2 2 2 2 5  25  2 2 2 2 2 2 2 2 2 2 5  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5  25  1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5  25  1 1 1 1 1 1 1 1 1 1 1 2 2 5 5  25  1 1 1 1 1 1 1 1 1 2 2 2 5 5  25  1 1 1 1 1 1 1 2 2 2 2 5 5  25  1 1 1 1 1 2 2 2 2 2 5 5  25  1 1 1 2 2 2 2 2 2 5 5  25  1 2 2 2 2 2 2 2 5 5  25  1 1 1 1 1 1 1 1 1 1 5 5 5  25  1 1 1 1 1 1 1 1 2 5 5 5  25  1 1 1 1 1 1 2 2 5 5 5  25  1 1 1 1 2 2 2 5 5 5  25  1 1 2 2 2 2 5 5 5  25  2 2 2 2 2 5 5 5  25  1 1 1 1 1 5 5 5 5  25  1 1 1 2 5 5 5 5  25  1 2 2 5 5 5 5  25  5 5 5 5 5  25  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10  25  1 1 1 1 1 1 1 1 1 1 1 1 1 2 10  25  1 1 1 1 1 1 1 1 1 1 1 2 2 10  25  1 1 1 1 1 1 1 1 1 2 2 2 10  25  1 1 1 1 1 1 1 2 2 2 2 10  25  1 1 1 1 1 2 2 2 2 2 10  25  1 1 1 2 2 2 2 2 2 10  25  1 2 2 2 2 2 2 2 10  25  1 1 1 1 1 1 1 1 1 1 5 10  25  1 1 1 1 1 1 1 1 2 5 10  25  1 1 1 1 1 1 2 2 5 10  25  1 1 1 1 2 2 2 5 10  25  1 1 2 2 2 2 5 10  25  2 2 2 2 2 5 10  25  1 1 1 1 1 5 5 10  25  1 1 1 2 5 5 10  25  1 2 2 5 5 10  25  5 5 5 10  25  1 1 1 1 1 10 10  25  1 1 1 2 10 10  25  1 2 2 10 10  25  5 10 10  25  1 1 1 1 1 20  25  1 1 1 2 20  25  1 2 2 20  25  5 20     each element can appear only once 4  2 2  10  1 2 2 5  10  10  25  1 2 2 20  25  5 20

User · Answer

I did not like the Javascript Solution I saw above  Here is the one I build using partial applying  closures and recursion  Ok  I was mainly concern about  if the combinations array could satisfy the target requirement  hopefully this approached you will start to find the rest of combinations Here just set the target and pass the combinations array  function main         const target   10     const getPermutationThatSumT   setTarget target      const permutation   getPermutationThatSumT  1  4  2  5  6  7        console log  permutation       the currently implementation I came up with function setTarget target        let partial            return function permute input            let i  removed          for  i   0  i  lt  input length  i                  removed   input splice i  1  0               partial push removed                const sum   partial reduce  a  b    gt  a   b              if  sum     target  return partial slice               if  sum  lt  target  permute input               input splice i  0  removed               partial pop                      return null

User · Answer

KeithBeller s answer with slightly changed variable names and some comments       public static void Main string   args                List lt int gt  input   new List lt int gt      3  9  8  4  5  7  10            int targetSum   15          SumUp input  targetSum              public static void SumUp List lt int gt  input  int targetSum                SumUpRecursive input  targetSum  new List lt int gt                 private static void SumUpRecursive List lt int gt  remaining  int targetSum  List lt int gt  listToSum                   Sum up partial         int sum   0          foreach  int x in listToSum              sum    x             Check sum matched         if  sum    targetSum              Console WriteLine  sum     string Join      listToSum ToArray             targetSum              Check sum passed         if  sum  gt   targetSum              return             Iterate each input character         for  int i   0  i  lt  remaining Count  i                            Build list of remaining items to iterate             List lt int gt  newRemaining   new List lt int gt                 for  int j   i   1  j  lt  remaining Count  j                    newRemaining Add remaining j                   Update partial list             List lt int gt  newListToSum   new List lt int gt  listToSum               int currentItem   remaining i               newListToSum Add currentItem               SumUpRecursive newRemaining  targetSum  newListToSum

User · Answer

I ported the C  sample to Objective-c and didn t see it in the responses     Usage NSMutableArray  numberList     NSMutableArray alloc  init   NSMutableArray  partial     NSMutableArray alloc  init   int target   16  for  int i   1  i lt target  i        numberList addObject   i       self findSums numberList target target part partial                                                                              Finds combinations of numbers that add up to target recursively                                                                       - void findSums  NSMutableArray  numbers target  int target part  NSMutableArray  partial       int s   0      for  NSNumber  x in partial        s     x intValue          if  s    target        NSLog   Sum       partial          if  s  gt   target        return         for  int i   0 i  lt   numbers count  i                   int n    numbers i  intValue           NSMutableArray  remaining     NSMutableArray alloc  init           for  int j   i   1  j  lt   numbers count  j               remaining addObject    numbers j  intValue                NSMutableArray  partRec     NSMutableArray alloc  initWithArray partial            partRec addObject   n             self findSums remaining target target part partRec

User · Answer

func sum array    Int   - gt  Int      var sum   0     array forEach    item  in         sum   item   sum           return sum   func susetNumbers array   Int   target   Int  subsetArray   Int  result   inout   Int    - gt    Int        let s   sum array  subsetArray      if s    target           print  quot sum  subsetArray      target  quot           result append subsetArray            for i in 0   lt array count          let n   array i          let remaning   Array array  i 1    lt array count           susetNumbers array  remaning  target  target  subsetArray  subsetArray    n   result   amp result                     return result     var resultArray     Int         let newA   susetNumbers array   1 2 3 4 5   target  5  subsetArray     result  amp resultArray      print resultArray

User · Answer

Another python solution would be to use the itertools combinations module as follows        usr local bin python  from itertools import combinations  def find sum in list numbers  target       results          for x in range len numbers            results extend                                   combo for combo in combinations numbers  x                        if sum combo     target                                    print results  if   name         main         find sum in list  3 9 8 4 5 7 10   15    Output    8  7    5  10    3  8  4    3  5  7

User · Answer

A Javascript version    x000D   x000D  function subsetSum numbers  target  partial    x000D    var s  n  remaining  x000D   x000D    partial   partial        x000D   x000D       sum partial x000D    s   partial reduce function  a  b    x000D      return a   b  x000D       0   x000D   x000D       check if the partial sum is equals to target x000D    if  s     target    x000D      console log   s  s   partial join       target  x000D      x000D   x000D    if  s  gt   target    x000D      return      if we reach the number why bother to continue x000D      x000D   x000D    for  var i   0  i  lt  numbers length  i      x000D      n   numbers i   x000D      remaining   numbers slice i   1   x000D      subsetSum remaining  target  partial concat  n     x000D      x000D    x000D   x000D  subsetSum  3 9 8 4 5 7 10  15   x000D   x000D     output  x000D     3 8 4 15 x000D     3 5 7 15 x000D     8 7 15 x000D     5 10 15 x000D   x000D   x000D

User · Answer

Thank you   ephemient   i have converted above logic from python to php       lt  php  data   array array 2 3 5 10 15  array 4 6 23 15 12  array 23 34 12 1 5     maxsum   25   print r bestsum  data  maxsum       function call  function bestsum  data  maxsum     res   array fill 0   maxsum   1   0     res 0    array                   base case foreach  data as  group      new res    res                  copy res    foreach  group as  ele          for  i 0  i lt   maxsum- ele 1   i                     if  res  i     0                         ele index    i  ele               new res  ele index     res  i                new res  ele index       ele                          res    new res      for  i  maxsum  i gt 0  i--          if  res  i   0                return  res  i           break            return array        gt

User · Answer

C   version of the same algorithm   include  lt iostream gt   include  lt list gt  void subset sum recursive std  list lt int gt  numbers  int target  std  list lt int gt  partial            int s   0          for  std  list lt int gt   const iterator cit   partial begin    cit    partial end    cit                          s     cit                    if s    target                            std  cout  lt  lt   sum                      for  std  list lt int gt   const iterator cit   partial begin    cit    partial end    cit                                          std  cout  lt  lt   cit  lt  lt                                         std  cout  lt  lt         lt  lt  target  lt  lt  std  endl                    if s  gt   target              return          int n          for  std  list lt int gt   const iterator ai   numbers begin    ai    numbers end    ai                          n    ai              std  list lt int gt  remaining              for std  list lt int gt   const iterator aj   ai  aj    numbers end    aj                                  if aj    ai continue                  remaining push back  aj                             std  list lt int gt  partial rec partial              partial rec push back n               subset sum recursive remaining target partial rec                 void subset sum std  list lt int gt  numbers int target        subset sum recursive numbers target std  list lt int gt        int main         std  list lt int gt  a      a push back  3   a push back  9   a push back  8       a push back  4       a push back  5       a push back  7       a push back  10       int n   15        std  cin  gt  gt  n      subset sum a  n       return 0

User · Answer

Very efficient algorithm using tables i wrote in c   couple a years ago   If you set PRINT 1 it will print all combinations but it wont be use the efficient method    Its so efficient that it calculate more than 10 14 combinations in less than 10ms    include  lt stdio h gt   include  lt stdlib h gt     include  CTime h    define SUM 300  define MAXNUMsSIZE 30   define PRINT 0   long long CountAddToSum int int   int const int   int   void printr const int    int   long long table1 SUM  MAXNUMsSIZE    int main         int Nums    3 4 5 6 7 9 13 11 12 13 22 35 17 14 18 23 33 54       int sum SUM      int size sizeof Nums  sizeof int       int i j a    0       long long N 0        CTime timer1       for i 0 i lt SUM   i           for j 0 j lt MAXNUMsSIZE   j               table1 i  j  -1       N   CountAddToSum sum Nums size a 0     algorithm       timer1 Get Passd           printf   nN  lld time   1f ms n   N timer1 Get Passd         printf   nN  lld  n   N       getchar        return 1     long long CountAddToSum int s  int arr   int arrsize  const int r   int rsize        static int totalmem 0  maxmem 0      int i  rnew      long long result1 0 result2 0       if s lt 0  return 0      if  table1 s  arrsize  gt 0  amp  amp  PRINT  0  return table1 s  arrsize       if s  0                if PRINT  printr r  rsize           return 1            if arrsize  0  return 0         else     rnew  int  malloc  rsize 1  sizeof int         for i 0 i lt rsize   i  rnew i  r i        rnew rsize  arr arrsize-1        result1    CountAddToSum s arr arrsize-1 rnew rsize       result2    CountAddToSum s-arr arrsize-1  arr arrsize rnew rsize 1       table1 s  arrsize  result1 result2      free rnew        return result1 result2      void printr const int r    int rsize        int lastr r 0  count 0 i      for i 0  i lt rsize   i                 if r i   lastr              count            else                       printf    d  d   count lastr               lastr r i               count 1                      if r i-1   lastr  printf    d  d   count lastr        printf   n

User · Answer

import java util     public class Main        int recursionDepth   0       private int     memo        public static void main String   args            int   nums   new int    5 2 4 3 1            int N   nums length           Main main    new Main             main memo   new int N 1  N 1            main  findCombo 0  N-1 nums  8  0  new LinkedList               System out println main recursionDepth                   private void  findCombo             int from             int to             int   nums             int targetSum             int currentSum             LinkedList lt Integer gt  list                if memo from  to     0                    currentSum   currentSum   memo from  to                              if currentSum  gt  targetSum                    return                             if currentSum     targetSum                    System out println  Found -    list                   return                             recursionDepth                for int i  from   i  lt   to  i                    list add nums i                   memo from  i    currentSum   nums i                   findCombo i 1  to nums  targetSum  memo from  i   list                   list removeLast

User · Answer

Here is a better version with better output formatting and C   11 features   void subset sum rec std  vector lt int gt   amp  nums  const int  amp  target  std  vector lt int gt   amp  partialNums         int currentSum   std  accumulate partialNums begin    partialNums end    0       if  currentSum  gt  target          return      if  currentSum    target                 std  cout  lt  lt   sum             for  auto it   partialNums begin    it    std  prev partialNums end       it              cout  lt  lt   it  lt  lt               cout  lt  lt   std  prev partialNums end             std  cout  lt  lt         lt  lt  target  lt  lt  std  endl            for  auto it   nums begin    it    nums end      it                 std  vector lt int gt  remaining          for  auto it2   std  next it   it2    nums end      it2              remaining push back  it2            std  vector lt int gt  partial   partialNums          partial push back  it           subset sum rec remaining  target  partial

User · Answer

Perl version  of the leading answer    use strict   sub subset sum     my   numbers   target   result   sum           print  sum   join        result        target n  if  sum     target    return if  sum  gt    target     subset sum    numbers      1       numbers     target                    result        numbers- gt         sum    numbers- gt           for  0       numbers      subset sum  3 9 8 4 5 7 10 6   15     Result   sum 3 8 4    15 sum 3 5 7    15 sum 9 6    15 sum 8 7    15 sum 4 5 6    15 sum 5 10    15   Javascript version    x000D   x000D  const subsetSum    numbers  target  partial       sum   0    gt    x000D    if  sum  lt  target  x000D      numbers forEach  num  i    gt  x000D        subsetSum numbers slice i   1   target  partial concat  num    sum   num    x000D    else if  sum    target  x000D      console log  sum  s     s   partial join    target   x000D    x000D   x000D  subsetSum  3 9 8 4 5 7 10 6   15   x000D   x000D   x000D    Javascript one-liner that actually returns results  instead of printing it     x000D   x000D  const subsetSum  n t p    s 0 r      gt  s lt t n forEach  l i   gt subsetSum n slice i 1  t     p l  s l r   s  t r push p  0 r   x000D   x000D  console log subsetSum  3 9 8 4 5 7 10 6   15    x000D   x000D   x000D    And my favorite  one-liner with callback    x000D   x000D  const subsetSum  n t cb p    s 0   gt s lt t n forEach  l i   gt subsetSum n slice i 1  t cb     p l  s l   s  t cb p  0  x000D   x000D  subsetSum  3 9 8 4 5 7 10 6   15  console log   x000D   x000D   x000D

User · Answer

PHP Version  as inspired by Keith Beller s C  version   bala s PHP version did not work for me  because I did not need to group numbers  I wanted a simpler implementation with one target value  and a pool of numbers  This function will also prune any duplicate entries          Calculates a subset sum  finds out which combinations of numbers    from the numbers array can be added together to come to the target    number         Returns an indexed array with arrays of number combinations         Example           lt pre gt      matches   subset sum array 5 10 7 3 20   25       lt  pre gt         Returns          lt pre gt     Array            0    gt  Array                  0    gt  3           1    gt  5           2    gt  7           3    gt  10              1    gt  Array                  0    gt  5           1    gt  20                 lt  pre gt          param number    numbers     param number  target     param array  part     return array number        function subset sum  numbers   target   part null           we assume that an empty  part variable means this        is the top level call       toplevel   false      if  part     null             toplevel   true           part   array                s   0      foreach  part as  x                  s    s    x                we have found a match      if  s     target                 sort  part      ensure the numbers are always sorted         return array implode       part                  gone too far  break off     if  s  gt    target                 return null              matches   array         totalNumbers   count  numbers        for  i 0   i  lt   totalNumbers   i                    remaining   array             n    numbers  i            for  j    i 1   j  lt   totalNumbers   j                            remaining      numbers  j                       part rec    part           part rec      n            result   subset sum  remaining   target   part rec           if  result                          matches   array merge  matches   result                        if   toplevel                 return  matches                this is the top level function call  we have to        prepare the final result value by stripping any        duplicate results       matches   array unique  matches        result   array        foreach  matches as  entry                  result     explode       entry              return  result

User · Answer

This can be used to print all the answers as well  public void recur int   a  int n  int sum  int   ans  int ind        if  n  lt  0  amp  amp  sum    0          return      if  n  lt  0  amp  amp  sum    0            print ans  ind           return            if  sum  gt   a n             ans ind    a n           recur a  n - 1  sum - a n   ans  ind   1             recur a  n - 1  sum  ans  ind      public void print int   a  int n        for  int i   0  i  lt  n  i            System out print a i              System out println        Time Complexity is exponential  Order of 2 n

User · Answer

This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target  Here is the algorithm in Python   def subset sum numbers  target  partial          s   sum partial         check if the partial sum is equals to target     if s    target           print  sum  s   s     partial  target      if s  gt   target          return    if we reach the number why bother to continue      for i in range len numbers            n   numbers i          remaining   numbers i 1           subset sum remaining  target  partial    n      if   name         main         subset sum  3 9 8 4 5 7 10  15        Outputs       sum  3  8  4   15      sum  3  5  7   15      sum  8  7   15      sum  5  10   15   This type of algorithms are very well explained in the following Standford s Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions   Edit  The above as a generator function  making it a bit more useful  Requires Python 3 3  because of yield from   def subset sum numbers  target  partial     partial sum 0       if partial sum    target          yield partial     if partial sum  gt   target          return     for i  n in enumerate numbers           remaining   numbers i   1           yield from subset sum remaining  target  partial    n   partial sum   n    Here is the Java version of the same algorithm   package tmp   import java util ArrayList  import java util Arrays   class SumSet       static void sum up recursive ArrayList lt Integer gt  numbers  int target  ArrayList lt Integer gt  partial           int s   0         for  int x  partial  s    x         if  s    target              System out println  sum   Arrays toString partial toArray         target          if  s  gt   target              return         for int i 0 i lt numbers size   i                   ArrayList lt Integer gt  remaining   new ArrayList lt Integer gt                  int n   numbers get i                for  int j i 1  j lt numbers size   j    remaining add numbers get j                 ArrayList lt Integer gt  partial rec   new ArrayList lt Integer gt  partial                partial rec add n                sum up recursive remaining target partial rec                      static void sum up ArrayList lt Integer gt  numbers  int target            sum up recursive numbers target new ArrayList lt Integer gt                public static void main String args              Integer   numbers    3 9 8 4 5 7 10           int target   15          sum up new ArrayList lt Integer gt  Arrays asList numbers   target             It is exactly the same heuristic  My Java is a bit rusty but I think is easy to understand   C  conversion of Java solution   by  JeremyThompson   public static void Main string   args        List lt int gt  numbers   new List lt int gt      3  9  8  4  5  7  10        int target   15      sum up numbers  target      private static void sum up List lt int gt  numbers  int target        sum up recursive numbers  target  new List lt int gt         private static void sum up recursive List lt int gt  numbers  int target  List lt int gt  partial        int s   0      foreach  int x in partial  s    x       if  s    target          Console WriteLine  sum     string Join      partial ToArray             target        if  s  gt   target          return       for  int i   0  i  lt  numbers Count  i                  List lt int gt  remaining   new List lt int gt             int n   numbers i           for  int j   i   1  j  lt  numbers Count  j    remaining Add numbers j             List lt int gt  partial rec   new List lt int gt  partial           partial rec Add n           sum up recursive remaining  target  partial rec             Ruby solution   by  emaillenin   def subset sum numbers  target  partial       s   partial inject 0       check if the partial sum is equals to target    puts  sum   partial     target   if s    target    return if s  gt   target   if we reach the number why bother to continue     0   numbers length - 1   each do  i      n   numbers i      remaining   numbers drop i 1      subset sum remaining  target  partial    n     end end  subset sum  3 9 8 4 5 7 10  15    Edit  complexity discussion  As others mention this is an NP-hard problem  It can be solved in exponential time O 2 n   for instance for n 10 there will be 1024 possible solutions  If the targets you are trying to reach are in a low range then this algorithm works  So for instance   subset sum  1 2 3 4 5 6 7 8 9 10  100000  generates 1024 branches because the target never gets to filter out possible solutions   On the other hand subset sum  1 2 3 4 5 6 7 8 9 10  10  generates only 175 branches  because the target to reach 10 gets to filter out many combinations   If N and Target are big numbers one should move into an approximate version of the solution

User · Answer

Excel VBA version below   I needed to implement this in VBA  not my preference  don t judge me    and used the answers on this page for the approach   I m uploading in case others also need a VBA version   Option Explicit  Public Sub SumTarget       Dim numbers 0 To 6   As Long     Dim target As Long      target   15     numbers 0    3  numbers 1    9  numbers 2    8  numbers 3    4  numbers 4    5     numbers 5    7  numbers 6    10      Call SumUpTarget numbers  target  End Sub  Public Sub SumUpTarget numbers   As Long  target As Long      Dim part   As Long     Call SumUpRecursive numbers  target  part  End Sub  Private Sub SumUpRecursive numbers   As Long  target As Long  part   As Long       Dim s As Long  i As Long  j As Long  num As Long     Dim remaining   As Long  partRec   As Long     s   SumArray part       If s   target Then Debug Print  SUM      amp  ArrayToString part   amp           amp  target     If s  gt   target Then Exit Sub      If  Not Not numbers   lt  gt  0 Then         For i   0 To UBound numbers              Erase remaining               num   numbers i              For j   i   1 To UBound numbers                  AddToArray remaining  numbers j              Next j             Erase partRec               CopyArray partRec  part             AddToArray partRec  num             SumUpRecursive remaining  target  partRec         Next i     End If  End Sub  Private Function ArrayToString x   As Long  As String     Dim n As Long  result As String     result        amp  x n      For n   LBound x    1 To UBound x          result   result  amp       amp  x n      Next n     result   result  amp          ArrayToString   result End Function  Private Function SumArray x   As Long  As Long     Dim n As Long     SumArray   0     If  Not Not x   lt  gt  0 Then         For n   LBound x  To UBound x              SumArray   SumArray   x n          Next n     End If End Function  Private Sub AddToArray arr   As Long  x As Long      If  Not Not arr   lt  gt  0 Then         ReDim Preserve arr 0 To UBound arr    1      Else         ReDim Preserve arr 0 To 0      End If     arr UBound arr     x End Sub  Private Sub CopyArray destination   As Long  source   As Long      Dim n As Long     If  Not Not source   lt  gt  0 Then         For n   0 To UBound source                  AddToArray destination  source n          Next n     End If End Sub   Output  written to the Immediate window  should be   SUM    3 8 4      15 SUM    3 5 7      15 SUM    8 7      15 SUM    5 10      15

User · Answer

The solution of this problem has been given a million times on the Internet  The problem is called The coin changing problem  One can find solutions at http   rosettacode org wiki Count the coins and mathematical model of it at http   jaqm ro issues volume-5 issue-2 pdfs patterson harmel pdf  or Google coin change problem    By the way  the Scala solution by Tsagadai  is interesting  This example produces either 1 or 0  As a side effect  it lists on the console all possible solutions  It displays the solution  but fails making it usable in any way   To be as useful as possible  the code should return a List List Int  in order to allow getting the number of solution  length of the list of lists   the  best  solution  the shortest list   or all the possible solutions   Here is an example  It is very inefficient  but it is easy to understand     object Sum extends App      def sumCombinations total  Int  numbers  List Int    List List Int            def add x   Int  List List Int     y   Int  List List Int       Int  List List Int               x  1   y  1  x  2     y  2             def sumCombinations resultAcc  List List Int    sumAcc  List Int   total  Int  numbers  List Int     Int  List List Int              if  numbers isEmpty    total  lt  0             0  resultAcc          else if  total    0             1  sumAcc    resultAcc          else           add sumCombinations resultAcc  sumAcc  total  numbers tail   sumCombinations resultAcc  numbers head    sumAcc  total - numbers head  numbers                      sumCombinations Nil  Nil  total  numbers sortWith    gt       2        println sumCombinations 15  List 1  2  5  10   mkString   n       When run  it displays   List 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  List 1  1  1  1  1  1  1  1  1  1  1  1  1  2  List 1  1  1  1  1  1  1  1  1  1  1  2  2  List 1  1  1  1  1  1  1  1  1  2  2  2  List 1  1  1  1  1  1  1  2  2  2  2  List 1  1  1  1  1  2  2  2  2  2  List 1  1  1  2  2  2  2  2  2  List 1  2  2  2  2  2  2  2  List 1  1  1  1  1  1  1  1  1  1  5  List 1  1  1  1  1  1  1  1  2  5  List 1  1  1  1  1  1  2  2  5  List 1  1  1  1  2  2  2  5  List 1  1  2  2  2  2  5  List 2  2  2  2  2  5  List 1  1  1  1  1  5  5  List 1  1  1  2  5  5  List 1  2  2  5  5  List 5  5  5  List 1  1  1  1  1  10  List 1  1  1  2  10  List 1  2  2  10  List 5  10    The sumCombinations   function may be used by itself  and the result may be further analyzed to display the  best  solution  the shortest list   or the number of solutions  the number of lists    Note that even like this  the requirements may not be fully satisfied  It might happen that the order of each list in the solution be significant  In such a case  each list would have to be duplicated as many time as there are combination of its elements  Or we might be interested only in the combinations that are different   For example  we might consider that List 5  10  should give two combinations  List 5  10  and List 10  5   For List 5  5  5  it could give three combinations or one only  depending on the requirements  For integers  the three permutations are equivalent  but if we are dealing with coins  like in the  coin changing problem   they are not   Also not stated in the requirements is the question of whether each number  or coin  may be used only once or many times  We could  and we should   generalize the problem to a list of lists of occurrences of each number  This translates in real life into  what are the possible ways to make an certain amount of money with a set of coins  and not a set of coin values    The original problem is just a particular case of this one  where we have as many occurrences of each coin as needed to make the total amount with each single coin value

User · Answer

Deduce 0 in the first place  Zero is an identiy for addition so it is useless by the monoid laws in this particular case  Also deduce negative numbers as well if you want to climb up to a positive number  Otherwise you would also need subtraction operation   So    the fastest algorithm you can get on this particular job is as follows given in JS    x000D   x000D  function items2T  n    ns  t   x000D      var c      t n   x000D      return ns length   Array c 1  fill   x000D                                    reduce  r   i    gt  r concat items2T ns  t-n i  map s   gt  Array i  fill n  concat s        x000D                         t   n      x000D                                  Array c  fill n    x000D     x000D   x000D  var data    3  9  8  4  5  7  10   x000D      result  x000D   x000D  console time  combos    x000D  result   items2T data  15   x000D  console timeEnd  combos    x000D  console log JSON stringify result    x000D   x000D   x000D    This is a very fast algorithm but if you sort the data array descending it will be even faster  Using  sort   is insignificant since the algorithm will end up with much less recursive invocations

User · Answer

To find the combinations using excel -  its fairly easy    You computer must not be too slow    Go to this site    Go to the  Sum to Target  page  Download the  Sum to Target  excel file   Follow the directions on the website page    hope this helps

User · Answer

Recommended as an answer   Here s a solution using es2015 generators   function  subsetSum numbers  target  partial       partialSum   0       if partialSum     target  yield partial    if partialSum  gt   target  return    for let i   0  i  lt  numbers length  i         const remaining   numbers slice i   1            n   numbers i       yield  subsetSum remaining  target      partial  n   partialSum   n           Using generators can actually be very useful because it allows you to pause script execution immediately upon finding a valid subset  This is in contrast to solutions without generators  ie lacking state  which have to iterate through every single subset of numbers

[algorithm] Finding all possible combinations of numbers to reach a given sum

Examples related to algorithm

Examples related to search

Examples related to language-agnostic

Examples related to combinations

Examples related to subset-sum