Getting all possible sums that add up to a given number

Question

I'm making an math app for the android. In one of these fields the user can enter an int (no digits and above 0). The idea is to get all possible sums that make this int, without doubles (4+1 == 1+4 in this case). The only thing known is this one int.

For example:

Say the user enters 4, I would like the app to return:

• 4
• 3+1
• 2+2
• 2+1+1
• 1+1+1+1

Obviously 4 == 4 so that should be added too. Any suggestions as to how i should go about doing this?

• Yashwanth Kumar: it would be better if you can add algorithm flag
• Nikunj Patel: what about 5 ? :::: 5 4+1 2.5 + 2.5 ? 1+1+1+1+1
• borrible: You should be aware that the number of partitions of a number grows quickly. By 22 there are already over 1000 partitions and by the time you reach 100 you are looking at around 190,000,000 partitions.
• Manuel: @nik Nope only whole numbers (as it says no digits)
• HomeworkHopper: Technically, the int is the" sum". The numbers that add up to a sum are called "addends"

Answer 1

Here's a simple algorithm that purports to do that

from : http://introcs.cs.princeton.edu/java/23recursion/Partition.java.html

public class Partition { 
 public static void partition(int n) {
 partition(n, n, "");
 }
 public static void partition(int n, int max, String prefix) {
 if (n == 0) {
 StdOut.println(prefix);
 return;
 }
 for (int i = Math.min(max, n); i >= 1; i--) {
 partition(n-i, i, prefix + " " + i);
 }
 }
 public static void main(String[] args) { 
 int N = Integer.parseInt(args[0]);
 partition(N);
 }
}

Answer 2

There are short and elegant recursive solution to generate them, but the following may be easier to use and implement in existing code:

import java.util.*;
public class SumIterator implements Iterator<List<Integer>>, Iterable<List<Integer>> {
 // keeps track of all sums that have been generated already
 private Set<List<Integer>> generated;
 // holds all sums that haven't been returned by `next()`
 private Stack<List<Integer>> sums;
 public SumIterator(int n) {
 // first a sanity check...
 if(n < 1) {
 throw new RuntimeException("'n' must be >= 1");
 }
 generated = new HashSet<List<Integer>>();
 sums = new Stack<List<Integer>>();
 // create and add the "last" sum of size `n`: [1, 1, 1, ... , 1]
 List<Integer> last = new ArrayList<Integer>();
 for(int i = 0; i < n; i++) {
 last.add(1);
 }
 add(last);
 // add the first sum of size 1: [n]
 add(Arrays.asList(n));
 }
 private void add(List<Integer> sum) {
 if(generated.add(sum)) {
 // only push the sum on the stack if it hasn't been generated before
 sums.push(sum);
 }
 }
 @Override
 public boolean hasNext() {
 return !sums.isEmpty();
 }
 @Override
 public Iterator<List<Integer>> iterator() {
 return this;
 }
 @Override
 public List<Integer> next() {
 List<Integer> sum = sums.pop(); // get the next sum from the stack
 for(int i = sum.size() - 1; i >= 0; i--) { // loop from right to left
 int n = sum.get(i); // get the i-th number
 if(n > 1) { // if the i-th number is more than 1
 for(int j = n-1; j > n/2; j--) { // if the i-th number is 10, loop from 9 to 5
 List<Integer> copy = new ArrayList<Integer>(sum); // create a copy of the current sum
 copy.remove(i); // remove the i-th number
 copy.add(i, j); // insert `j` where the i-th number was
 copy.add(i + 1, n-j); // insert `n-j` next to `j`
 add(copy); // add this new sum to the stack
 } // 
 break; // stop looping any further
 } 
 }
 return sum;
 }
 @Override
 public void remove() {
 throw new UnsupportedOperationException();
 }
}

You can use it like this:

int n = 10;
for(List<Integer> sum : new SumIterator(n)) {
 System.out.println(n + " = " + sum);
}

which would print:

10 = [10]
10 = [6, 4]
10 = [6, 3, 1]
10 = [6, 2, 1, 1]
10 = [7, 3]
10 = [7, 2, 1]
10 = [8, 2]
10 = [9, 1]
10 = [5, 4, 1]
10 = [5, 3, 1, 1]
10 = [5, 2, 1, 1, 1]
10 = [8, 1, 1]
10 = [7, 1, 1, 1]
10 = [4, 3, 1, 1, 1]
10 = [4, 2, 1, 1, 1, 1]
10 = [6, 1, 1, 1, 1]
10 = [5, 1, 1, 1, 1, 1]
10 = [3, 2, 1, 1, 1, 1, 1]
10 = [4, 1, 1, 1, 1, 1, 1]
10 = [3, 1, 1, 1, 1, 1, 1, 1]
10 = [2, 1, 1, 1, 1, 1, 1, 1, 1]
10 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

• Manuel: Very nice code, but the one from Ashkan Aryan is cleaner, and as this is for a client that likes clean code I'll use that one. I upvoted you tho becouse its a very nice piece of code!
• CTMacUser: The code misses combinations where a number besides 1 repeats (5+5, 6+2+2, 3+3+3+1, 4+4+2, etc).

Answer 3

This is the mathematical concept known as partitions. In general, it's... difficult, but there are techniques for small numbers. A load of useful stuff linked from the wiki page.

Answer 4

For a number N you know that the max number of terms is N. so, you will start by enumerating all those possibilities.

For each possible number of terms, there are a number of possibilities. The formula eludes me now, but basically, the idea is to start by (N+1-i + 1 + ... + 1) where i is the number of terms, and to move 1s from left to right, second case would be (N-i + 2 + ... + 1) until you cannot do another move without resulting in an unsorted combination.

(Also, why did you tagged this android again?)

• Manuel: because it is for an app, doesn't really affect the algorithm tho... :)

Answer 5

This is related to the subset sum problem algorithm.

N = {N*1, (N-1)+1, (N-2)+2, (N-3)+3 .., N-1 = {(N-1), ((N-1)-1)+2, ((N-1)-1)+3..}

etc.

So it's a recursive function involving substitution; whether that makes sense or not when dealing with large numbers, however, is something you'll have to decide for yourself.

Answer 6

All of these solutions seem a little complex. This can be achieved by simply "incrementing" a list initialized to contain 1's=N.

If people don't mind converting from c++, the following algorithm produces the needed output.

bool next(vector<unsigned>& counts) {
 if(counts.size() == 1)
 return false;
 //increment one before the back
 ++counts[counts.size() - 2];
 //spread the back into all ones
 if(counts.back() == 1)
 counts.pop_back();
 else {
 //reset this to 1's
 unsigned ones = counts.back() - 1;
 counts.pop_back();
 counts.resize(counts.size() + ones, 1);
 }
 return true;
}
void print_list(vector<unsigned>& list) {
 cout << "[";
 for(unsigned i = 0; i < list.size(); ++i) {
 cout << list[i];
 if(i < list.size() - 1)
 cout << ", ";
 }
 cout << "]\n";
}
int main() {
 unsigned N = 5;
 vector<unsigned> counts(N, 1);
 do {
 print_list(counts);
 } while(next(counts));
 return 0;
}

for N=5 the algorithm gives the following

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3]
[1, 2, 1, 1]
[1, 2, 2]
[1, 3, 1]
[1, 4]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 3]
[3, 1, 1]
[3, 2]
[4, 1]
[5]