# [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 <= 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!`.