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

July 4, 2015 in JavaScript

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 <= n; ++i) { newTemp = temp + i; compositions(n - i, newTemp, output); } } }

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!`

.