← All posts

Algorithms / Partition a number to sum of smaller ones

The array x is to keep track of all possible integers we can find, the array t is to keep the sum t[i] of every x number from x[1] to x[i].

const n = 8;
let x = [1];
let t = [0];
 
const gen = (i) => {
    for (let j = x[i - 1]; j <= ~~((n - t[i - 1]) / 2); j++) {
        x[i] = j;
        t[i] = t[i - 1] + j;
        gen(i + 1);
    }
    x[i] = n - t[i - 1];
    debug(x.slice(1, i+1));
};
 
gen(1);

Now, let’s write a Generator algorithm with Backtracking.

Try every possible number from 1 to n, push them to an array x then check if it can sum up to n or not.

If it’s not, pop it out from the array x and try a different one.

To make sure we don’t have duplicate cases, we only select the result
array that are sorted.

const n = 8;
let x = [];
let count = 0;
 
const sum = x => x.reduce((t, i) => t + i, 0);
 
const isSorted = (x) => {
    let clone = x.map(i => i);
    clone.sort((a,b) => a - b);
    for (let i = 0; i < x.length; i++) {
        if (x[i] !== clone[i]) return false;
    }
    return true;
};
 
const gen = i => {
    for (let j = 1; j <= n; j++) {
        x[i] = j;
        if (sum(x) === n) {
            if (isSorted(x)) {
                debug(x);
            }
            break;
        }
        if (i < n) {
            gen(i + 1);
        }
        x.pop();
    }
};
 
gen(0);