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

This entry was posted in JavaScript and tagged , , , , by Hazem Saleh. Bookmark the permalink.

About Hazem Saleh

Hazem Saleh has more than eleven years of experience in Cloud, Mobile and Open Source technologies. He worked as a software engineer, technical leader, application architect, and technical consultant for many clients around the world. He is an Apache PMC (Project Management Committee) member and a person who spent many years of his life writing open source software. Beside being the author of the "JavaScript Unit Testing" book, "JavaScript Mobile Application Development" book, "Pro JSF and HTML5" book and the co-author of the "Definitive guide to Apache MyFaces" book, Hazem is also an author of many technical articles, a developerWorks contributing author and a technical speaker in both local and international conferences such as ApacheCon North America, Geecon, JavaLand, JSFDays, CON-FESS Vienna and JavaOne. Hazem is an XIBMer, he worked in IBM for ten years. Now, He is working for Nickelodeon New York as a Mobile Architect. He is also an OpenGroup Master Certified Specialist.