[JavaScript Quiz #15] All possible compositions of a number

Today’s JavaScript quiz is about finding all the possible compositions of a number. For example if we have a number 4, we would like to find all the possible compositions that sums up to 4 as follows.

1111
112
121
13
211
22
31
4

.

.

.

.

.

.

.

.

.

.

.

.

.

In order to develop this utility, it is important to understand its nature. For a number n, it has the following possible compositions:

n (for a composition length of 1)

1 n-1 (for a composition length of 2)

1 1 n-2 (for a composition of length 3)

…

1 1 1 … 1 (for a composition of length n)

This can be handled using recursive function as follows.

function compositions(n, temp, output) {
var i, newTemp;

if (n == 0) {
output.push(temp);
} else {
for (i = 1; i

As shown, the base is if n is equal to 0 then we add the temp string (which is initialized to "") to the output list, else we subtract i from n and adds i to the temp string. The following function getAllCompositions calls compositions with the initial values.

function getAllCompositions(n) {
var out = [];

compositions(n, "", out);

return out;
}

Finally, we can test getAllCompositions as follows.

// Test ...
var num = 4;
var out = getAllCompositions(num), i;

console.log("Compositions number for (" + num + ") = " + out.length);
for (i = 0; i < out.length; ++i) {
console.log(out[i]);
}

The output will be:

Compositions number for (4) = 8

1111
112
121
13
211
22
31
4

If you have a better solution, feel free to put in the comments below. The current solution complexity is n!.