#algorithm #dynamic-programming

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);
```

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);
```

If you think this note resonated, be it positive or negative, please feel free to send me an email and we can talk.