[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!.