Is there any Algorithm to Write a Number $N$ as a Sum of $M$ Natural Numbers?

Question

I have a number $N$ (for example $N=64$).

Is there any algorithm to find all the feasible ways for writing the number $N$ as a sum of $M$ positive numbers?

(For example $M=16$) --- Repetition is allowed.

$n_1 + n_2 + n_3 + ... + n_{16} = 64$
$n_i \ge 1$

Answer 1

This is the subset-sum problem -- it is NP-Complete, hence although there are certainly algorithms for it, none are necessarily "fast" in general (possibly for special cases of the problem though).

The most common approach is dynamic programming.

EDIT: while Wikipedia is unnecessarily general, as usual, the subset sum problem usually refers to OP's problem (i.e. restricted to positive integers) and is well-studied with several known solutions, such as dynamic programming. All of the following links give dynammic programming solutions to the subset sum problem when the restriction is to the positive integers.

http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/ http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf https://www.cs.cmu.edu/~ckingsf/class/02713-s13/lectures/lec15-subsetsum.pdf https://cseweb.ucsd.edu/classes/wi12/cse202-a/lecture7-final.pdf

Moreover, as also described in Cormen et al., and Kleinberg and Tardos, the Subset Sum problem refers to the restriction to the case of positive integers only. OP's $M$ constraint can be implemented easily by choosing a proper set of integers ($M$ copies of all integers less than or equal to $N-1$ will be sufficient, although strictly more than necessary).

Also all of the other answers given below just give pseudo-code for the dynamic programming solutions without explaining the provenance or the reasoning behind those choices. The links above, in contrast, explain the theory behind the idea in detail and how to specifically apply it to the subset sum problem, while retaining enough generality to allow OP to figure out how to fill in the details relevant for the implementation of their specific case.

Answer 2

function partitionCombination(N,m,p) {
    if (N == 0) print(p);
    else {
      L = p.length;
      for (i = m; i >= 1; i--) {
        p[L] = i;
        partitionCombination(N-i,i,p);
      }
      p.length = L;
    } 
}

 function partitionOrderCounts(N,p) {
    if (N == 0) print(p);
    else {
      L = p.length;
      for (i = N; i >= 1; i--) {
        p[L] = i;
        partitionOrderCounts(N-i,p);
      }
      p.length = L;
    } 
}
partitionCombination(8,8,[]);
partitionOrderCounts(8,[]);

Answer 3

You can use a recursive algorithm to iterate through the solutions, but there is an easy way to count them. The amount of non negative solutions to \begin{equation} x_1 + x_2 + \cdots + x_n = a \end{equation} is $a + n - 1 \choose n - 1$ or equivalently $a + n - 1 \choose a$. Since we want integer solutions, let $y_k = x_k + 1$. Each $y_k$ is now an integer. Re writing the top equation \begin{align} y_1 - 1 + y_2 - 1 + \cdots + y_n - 1 &= a\\ y_1 + y_2 + \cdots + y_n &= a + n \end{align} which still has $a + n - 1 \choose n - 1$ solutions. Let $a + n = N$ and $n = M$, then the equation \begin{equation} x_1 + x_2 + \cdots + x_M =N \end{equation} has $N - 1 \choose M - 1$ solutions.

Answer 4

This is the stars and bars problem. Imagine a line of $64$ stars and $63$ candidate bars between them. Pick $15$ of those bars to be real and read off the groupings. There are ${64 \choose 15}=122131734269895$ To make the list, there are many algorithms on the web to generate the combinations of $15$ choices out of $63$. For example, you can use the fact that ${63 \choose 15}={62 \choose 14}+{62 \choose 15}$, where the first are combinations that include the first bar (and hence have $1$ as the first summand) and the second are those that do not have the first bar (so the first summand is greater than $1$). This suggests a recursive algorithm.