Jay Taylor's notes

back to listing index

Finding all possible combinations of numbers to reach a given sum

[web search]
Original source (stackoverflow.com)
Tags: algorithms stackoverflow.com
Clipped on: 2016-05-28

How would you go about testing all possible combinations of additions from a given set of numbers so they add up to a given final number?

Example:

  • Set of numbers to add: {1,5,22,15,0,...}
  • Desired result: 12345

P.S: Asking this problem as maths isn't my forte and wondering how this could be adapted in code.

asked Jan 8 '11 at 4:26
Image (Asset 3/20) alt=
James Poulson
7,0301565111

protected by Community Jan 7 at 9:42

This question is protected to prevent "thanks!", "me too!", or spam answers by new users. To answer it, you must have earned at least 10 reputation on this site (the association bonus does not count).

4 upvote
  flag
Homework assignment? – dthorpe Jan 8 '11 at 4:37
4 upvote
  flag
The wikipedia article (en.wikipedia.org/wiki/Subset_sum_problem) even mentions that this problem is a good introduction to the class of NP-complete problems. – user57368 Jan 8 '11 at 4:42
1 upvote
  flag
@jmort253: I don't think there are any constraints other than having a set of integers which are positive and lower than the number given as a target. Any combination of numbers can be used. It isn't homework but the sort of problem that you'll be given to solve if you apply for some jobs. I can usually think up an algorithm when needed but I'm not sure how to view something like this. It needs to be decomposed somehow (recursive?). – James Poulson Jan 8 '11 at 5:14
2 upvote
  flag
@James, Do you need the combinations or just the number of subset's that add upto the sum? – st0le Jan 8 '11 at 5:39
1 upvote
  flag
Can we use the same element of the original set more than once? For example if the input is {1,2,3,5} and target 10, is 5 + 5 = 10 an acceptable solution? – antonis_wrx Aug 23 '15 at 0:29
up vote 98 down vote accepted

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 >= 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 >= 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<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(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<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(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 >= 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 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.

answered Jan 8 '11 at 10:50
Image (Asset 5/20) alt=
msalvadores
10.4k11744
   upvote
  flag
Thanks for the insights on complexity. This is probably something I should read up on. – James Poulson Jan 14 '11 at 8:47
   upvote
  flag
@Eric thanks for the edit. Good stuff. – msalvadores Dec 21 '13 at 21:22
   upvote
  flag
Java optimization: ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial); partial_rec.add(n); this does a copy of partial. and thus adds O(N). A better way is to just "partial.add(n)" do the recursion and then "partial.remove(partial.size -1). I reran your code to make sure. It works fine – Christian Bongiorno Apr 20 '15 at 0:10
   upvote
  flag
Python: SyntaxError: invalid syntax – Martha James Jul 31 '15 at 14:18
   upvote
  flag
This solution does not work for all cases. Consider [1, 2, 0, 6, -3, 3], 3 - it only outputs [1,2], [0,3], [3] while missing cases such as [6, -3, 3] – LiraNuna Mar 11 at 19:25

In Haskell:

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

And J:

(]#~12345=+/@>)(]<@#~[:#:@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?

answered Jan 8 '11 at 5:31
Image (Asset 6/20) alt=
ephemient
113k26169298
2 upvote
  flag
Wow, that's some pretty concise code. I'm fine with your answer. I think I just need to read up a bit on algorithms in general. I'll have a look at the syntax of the two languages as you've sparked my curiosity. – James Poulson Jan 14 '11 at 8:44
   upvote
  flag
I just installed Haskell to try this out, definitely can't just paste it in and have it execute, not in scope: 'subsequences' any pointers? – Hart CO Feb 6 '14 at 21:36

The solution of this problem has been given one 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 effects, 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 < 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(_ > _))._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 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 by the combination 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!) generalized 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.

answered Nov 20 '12 at 10:31
Image (Asset 7/20) alt=
2 upvote
  flag
This problem is not exactly the same as the coin change problem. OP is asking for all combination, not just the minimal. And, presumably, the integers in the set can be negative. Hence, certain optimizations of the coin change problem are not possible with this problem. – ThomasMcLeod Mar 20 '13 at 14:24
1 upvote
  flag
and also this problem allows repetition of items, I'm not sure OP wanted this, but more a knapsack problem – crl Mar 25 '14 at 14:16

C# version of @msalvadores code answer

void Main()
{
    int[] numbers = {3,9,8,4,5,7,10};
    int target = 15;
    sum_up(new List<int>(numbers.ToList()),target);
}

static void sum_up_recursive(List<int> numbers, int target, List<int> part)
{
   int s = 0;
   foreach (int x in part)
   {
       s += x;
   }
   if (s == target)
   {
        Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target);
   }
   if (s >= target)
   {
        return;
   }
   for (int i = 0;i < numbers.Count;i++)
   {
         var remaining = new List<int>();
         int n = numbers[i];
         for (int j = i + 1; j < numbers.Count;j++)
         {
             remaining.Add(numbers[j]);
         }
         var part_rec = new List<int>(part);
         part_rec.Add(n);
         sum_up_recursive(remaining,target,part_rec);
   }
}
static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers,target,new List<int>());
}
answered May 8 '12 at 20:25
Image (Asset 8/20) alt=
Keith Beller
667819

A Javascript version:

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target) {
    return;  // if we reach the number why bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([3,9,8,4,5,7,10],15);

// output:
// 3+8+4=15
// 3+5+7=15
// 8+7=15
// 5+10=15

answered Jun 16 '15 at 14:30
Image (Asset 9/20) alt=
rbarilani
9732810

C++ version of the same algorithm

#include <iostream>
#include <list>
void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial)
{
        int s = 0;
        for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
        {
            s += *cit;
        }
        if(s == target)
        {
                std::cout << "sum([";

                for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
                {
                    std::cout << *cit << ",";
                }
                std::cout << "])=" << target << std::endl;
        }
        if(s >= target)
            return;
        int n;
        for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
        {
            n = *ai;
            std::list<int> remaining;
            for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
            {
                if(aj == ai)continue;
                remaining.push_back(*aj);
            }
            std::list<int> partial_rec=partial;
            partial_rec.push_back(n);
            subset_sum_recursive(remaining,target,partial_rec);

        }
}

void subset_sum(std::list<int> numbers,int target)
{
    subset_sum_recursive(numbers,target,std::list<int>());
}
int main()
{
    std::list<int> 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 >> n;
    subset_sum(a, n);
    return 0;
}
answered Mar 19 '13 at 10:09
user1436489
Thank you.. ephemient

i have converted above logic from python to php..

<?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<($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>0;$i--)
  {
    if($res[$i]!=0)
    {
        return $res[$i];
        break;
    }
  }
return array();
}
?>
answered Jan 26 '12 at 19:31
Image (Asset 10/20) alt=
bala
94226
   upvote
  flag
Thanks @bala :) – James Poulson Feb 19 '12 at 0:13

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(_ < _), List())
}

def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = {
  if (target == 0) {println(solution); 1 }
  else if (target < 0 || numbers.length == 0) 0
  else 
    cc(target, numbers.tail, solution) 
    + cc(target - numbers.head, numbers, numbers.head :: solution)
}

To use it:

 > findSumCombinations(12345, List(1,5,22,15,0,..))
 * Prints a whole heap of lists that will sum to the target *
answered Sep 21 '12 at 7:19
Image (Asset 11/20) alt=
Tsagadai
6521721

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<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>=coins.length)
        return 0;

    int sumNow=curSum+coins[index];
    if (sumNow>Sum)
        return 0;
    if (sumNow==Sum)
        return 1;

    for (int i= index+1;i<coins.length;i++)
        count+=Count(Sum,coins,i,sumNow);

    return count;       
}
}
answered Aug 7 '13 at 2:55
Image (Asset 13/20) alt=
DJ'
27143

To find the combinations using excel - (its fairly easy). (You computer must not be too slow)

  1. Go to this site
  2. Go to the "Sum to Target" page
  3. Download the "Sum to Target" excel file.

    Follow the directions on the website page.

hope this helps.

answered Nov 30 '12 at 21:56
Image (Asset 15/20) alt=

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)]

answered May 15 '12 at 21:21
Image (Asset 16/20) alt=

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 <stdio.h>
#include <stdlib.h>
//#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<SUM;++i) 
        for(j=0;j<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<0) return 0;
    if (table1[s][arrsize]>0 && 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<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<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");

}
answered Oct 16 '13 at 11:45
Image (Asset 17/20) alt=

@KeithBeller's answer with slightly changed variable names and some comments.

    public static void Main(string[] args)
    {
        List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
        int targetSum = 15;
        SumUp(input, targetSum);
    }

    public static void SumUp(List<int> input, int targetSum)
    {
        SumUpRecursive(input, targetSum, new List<int>());
    }

    private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> 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 >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.Count; i++)
        {
            //Build list of remaining items to iterate
            List<int> newRemaining = new List<int>();
            for (int j = i + 1; j < remaining.Count; j++)
                newRemaining.Add(remaining[j]);

            //Update partial list
            List<int> newListToSum = new List<int>(listToSum);
            int currentItem = remaining[i];
            newListToSum.Add(currentItem);
            SumUpRecursive(newRemaining, targetSum, newListToSum);
        }
    }'
answered Mar 28 '15 at 19:37
Image (Asset 19/20) alt=
strider
83731231

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<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 >= target)
    { return; }

    for (int i = 0;i < [numbers count];i++ )
    {
        int n = [numbers[i] intValue];
        NSMutableArray* remaining = [[NSMutableArray alloc] init];
        for (int j = i + 1; j < [numbers count];j++)
        { [remaining addObject:@([numbers[j] intValue])]; }

        NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial];
        [partRec addObject:@(n)];
        [self findSums:remaining target:target part:partRec];
    }
}
answered Jan 6 at 16:18
Image (Asset 20/20) alt=
   upvote
  flag
If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. - From Review – fish_ball Jan 7 at 1:01

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 ( " & ArrayToString(part) & " ) = " & target
    If s >= target Then Exit Sub

    If (Not Not numbers) <> 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 = "{" & x(n)
    For n = LBound(x) + 1 To UBound(x)
        result = result & "," & x(n)
    Next n
    result = result & "}"
    ArrayToString = result
End Function

Private Function SumArray(x() As Long) As Long
    Dim n As Long
    SumArray = 0
    If (Not Not x) <> 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) <> 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) <> 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 
answered Jan 12 '14 at 14:55

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 < 0 && sum != 0)
        return;
    if (n < 0 && sum == 0) {
        print(ans, ind);
        return;
    }
    if (sum >= 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 < n; i++)
        System.out.print(a[i] + " ");
    System.out.println();
}

Time Complexity is exponential. Order of 2^n

answered May 13 at 0:45

Your Answer

asked

5 years ago

viewed

122177 times

active

15 days ago

Visit Chat

Hot Network Questions

Technology Life / Arts Culture / Recreation Science Other
  1. Stack Overflow
  2. Server Fault
  3. Super User
  4. Web Applications
  5. Ask Ubuntu
  6. Webmasters
  7. Game Development
  8. TeX - LaTeX
  1. Programmers
  2. Unix & Linux
  3. Ask Different (Apple)
  4. WordPress Development
  5. Geographic Information Systems
  6. Electrical Engineering
  7. Android Enthusiasts
  8. Information Security
  1. Database Administrators
  2. Drupal Answers
  3. SharePoint
  4. User Experience
  5. Mathematica
  6. Salesforce
  7. ExpressionEngine® Answers
  8. more (13)
  1. Photography
  2. Science Fiction & Fantasy
  3. Graphic Design
  4. Movies & TV
  5. Seasoned Advice (cooking)
  6. Home Improvement
  7. Personal Finance & Money
  8. Academia
  9. more (9)
  1. English Language & Usage
  2. Skeptics
  3. Mi Yodeya (Judaism)
  4. Travel
  5. Christianity
  6. Arqade (gaming)
  7. Bicycles
  8. Role-playing Games
  9. more (21)
  1. Mathematics
  2. Cross Validated (stats)
  3. Theoretical Computer Science
  4. Physics
  5. MathOverflow
  6. Chemistry
  7. Biology
  8. more (5)
  1. Stack Apps
  2. Meta Stack Exchange
  3. Area 51
  4. Stack Overflow Careers
site design / logo © 2016 Stack Exchange Inc; user contributions licensed under cc by-sa 3.0 with attribution required
rev 2016.5.27.3620