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

Today’s JavaScript quiz is about finding all the possible subsets of a number. For example if we have a number 4, we would like to find all the possible subsets 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 subsets:

n (for a subset length of 1)

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

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

…

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

This can be handled using recursive backtracking as follows.

function subsets(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 0) to the output list, else we subtract i from n and adds i to the temp string. The following function getAllSubsets calls subsets with the initial values.

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

subsets(n, "", out);

return out;
}

Finally, we can test getAllSubsets as follows.

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

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

The output will be:

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