/home/huy/everyday

# 12.26.2021 - 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);