Find all ways to sum given number (with repetitions allowed) from given set

Question

Given an array (e.g. [1,2]) of n elements and a number 'k' (e.g. 6), find all possible ways to produce the sum = k

For given example answer would be 4 because

1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2

The algorithm I could think of is by brute force, we simulate all possible scenarios, and stop when from given state we can not reach result.

 arr[] = [1,2]
    k = 6
   globalCount =0;
   function findSum(arr,k)
   {
      if(k ==0)
         globalCount++
         return
      else if(k<0)
         return

      for each i in arr{
       arr.erase(i)
       tmp = k
       findSum(arr,tmp)
       while(k>=0){
          findSum(arr,tmp -= i)
      } 
   }

I am not sure if my solution is most efficient one out there. Please comment /correct or show pointers to better solutions.

EDIT : Would really appreciate if someone can give me runtime complexity of my code and their soln code. :) Mine code complexity I think is Big-O( n^w ) w = k/avg(arr[0]..arr[n-1])

possible duplicate of [Generating the partitions of a number](http://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number) — templatetypedef, Sep 07 '11 at 21:15

score 5 · Accepted Answer · answered Sep 07 '11 at 20:10

If you're willing to excuse the fancy linq tricks, you might find this C# solution useful. Fortunately linq reads kind of like english. The idea is to build up the solutions as k starts from 0 and increments until it reaches its correct value. Each value of k builds on the previous solutions. One thing you have to watch for though is to ensure that the new "ways" you're finding are not re-orderings of others. I solved that by only counting them as valid if they're sorted. (which was only a single comparison)

void Main() {
    foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) {
        Console.WriteLine (string.Join(" ", way));
    }
}

int[][] GetSumWays(int[] array, int k) {
    int[][][] ways = new int[k + 1][][];
    ways[0] = new[] { new int[0] };

    for (int i = 1; i <= k; i++) {
        ways[i] = (
            from val in array
            where i - val >= 0
            from subway in ways[i - val]
            where subway.Length == 0 || subway[0] >= val
            select Enumerable.Repeat(val, 1)
                .Concat(subway)
                .ToArray()
        ).ToArray();
    }

    return ways[k];
}

Output:

1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2

It uses a dynamic programming approach and should be faster than a naive recursive approach. I think. I know it's fast enough to count the number of ways to break a dollar in a few milliseconds. (242)

+1 for code. Golly! if u hadnt told me, I wouldnt have known ever that it is a program that compiles and executes. That is so much like english. :) — Ajeet Ganga, Sep 07 '11 at 20:33

score 1 · Answer 2 · edited May 15 '22 at 08:17

1

This is an interesting subset of the partition problem. There's actually a closed-form solution to this (see here and here) if you allow all integers.

Doing some googling for the "restricted partition function" gave me some leads. This paper gives a pretty mathematically rigorous discussion of a couple of solutions to this problem, as does this one.

Unfortunately I'm too lazy to code these up. They're pretty intense solutions.

edited May 15 '22 at 08:17

Glorfindel

21,988
13
81
109

answered Sep 07 '11 at 19:32

AlexQueue

6,353
5
35
44

Thanks Queequeg, for finding the problem behind the problem. :) – Ajeet Ganga Sep 07 '11 at 20:34

score 0 · Answer 3 · edited May 24 '20 at 21:06

 static void populateSubsetSum(int[]a,int K,int runSum,int idx,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> al){
    if(idx>=a.length || runSum>K)
        return;
    if(runSum==K){
        ans.add(new ArrayList<>(al));
        return;
    }
    ArrayList<Integer> temp=new ArrayList<>(al);
    temp.add(a[idx]);
    populateSubsetSum(a,K,runSum+a[idx],idx,ans,temp);//when repitions of elements are allowed
    populateSubsetSum(a,K,runSum,idx+1,ans,al);
}

Call this function as:

populateSubsetSum(a,K,0,0,ans,new ArrayList<>());//array,sum,initial_sum,global 2d list,temp list

Find all ways to sum given number (with repetitions allowed) from given set

3 Answers3

Linked