如何写一个方法分析出一个正整数的和的所有可能性？

Question

比如一个函数

let plus = (num)=>{
    //方法
}

plus(10)

返回的结果是这样：

10 = 1+9；
10 = 1+2+3+4；
10 = 4+6；

总之就是返回这个参数所有的可能性。这个plus函数应该怎么写比较合适？

我的想法是用遍历一个[1,2,3,4,5,6,7,8,9,10]这样的数组，但是只能遍历固定的层数，比如说两层，三层，但是这样十分不灵活，求指教。

Answer 1

哎，好吧。Mask同学看出了问题，的确，那天写答案已经很晚就没有做去重。还是被人发现了。。。?

现在补上。

const num = 10
const statck = []
const obj = {}
const pow = num => num ** num

function reduce(upper, before = []) {
    for (let i = 1; i <= upper / 2; i++) {
        const diff = upper - i
        const arr = [i, diff, ...before]
        const id = arr.map(pow).reduce((pre, cur) => pre + cur)
        if (!obj[id]) {
            statck.push(arr)
            obj[id] = 1
        }
        if (diff > 1) reduce(diff, [...before, i])
    }
}

reduce(num)

const result = statck.map(a => '10 = ' + a.join(' + '))
console.log(result)

一共41种。

Answer 2

我现在想到的最快的方法应该是找到Z=1+2+3+...+X。。然后把1,2,3，...，X，做一个遍历和的组合，去掉有重复数字的，就应该是你想要的答案了。。比如10=1+2+3+4。。然后你就找到1,2,3,4的遍历和的组合。。

1. 1,2=3 3+4+3 （重复数字）
2. 1,3=4 2+4+4 （重复数字）
3. 1,4=5 2+3+5
4. 1,2,3=6 4+6
5. 1,2,4=7 3+7
6. 1,3,4=8 2+8
8. 2,3=5 1+4+5
9. 2,4=6 1+3+6
10. 2,3,4=9 1+9
.
.
.

这样子的形式。。

Answer 3

借鉴楼上的ciqulover提供的思路，感谢。
发现几个问题，按照他的解法，有许多重复值，所以10的和的正整数组成的可能组合并没有511种，而是通过过滤排序之后的41种。
所以重新写了一个，其中重要的是在递归里面循环遍历所有可能的值时，并不需要从头遍历到尾，比如

for(let i = 1; i < 10; i++) {}

而是遍历前半部分就可以了

for(let i = 1; i <= 10 / 2; i++) {} 

这里之所以取等号是因为当正整数为偶数时，可以分解成相等的两个数字，比如10 = 5 + 5。
还有取前半部分的原因是1 + 9和9 + 1组成实际上的结果是一样的。

对首次生成的结果进行数组过滤和排序等等，得出下列代码：

let results = [];

function plus(num, current = []) {
  let middle = num / 2;
  for (let i = 1; i <= middle; i++) {
    let j = num - i;
    let now = current.concat([i, j]);

    results.push(now);

    if (j > 1) {
      // 继续分解j
      let next = current.concat([i]);
      plus(j, next);
    }
  }
}

// 过滤掉相同的值
function filterSameValueArray(arr) {
  arr = arr.map((item) => {
    return item.sort().join(',');
  });

  return Array.from(new Set(arr))
    .map((item) => {
      return item.split(',');
    });
}

plus(10);

// 按长度排序
results = results.sort( (a, b) => {
  return a.length - b.length; // 负值代表谁应该在前面
});


results = filterSameValueArray(results).map(item => {
  return item.join(' + ');
});

console.log(`10的所有和的组成结果有${results.length}种，分别是：`);
console.log(results);

结果测试

注意几个点，关于数组的拷贝问题，concat拼接新数组不会对原数组造成污染，这里仅限于其数组元素没有对对象的引用。而splice()会对原数组造成污染，倘若数组元素里面有对对象的引用的话，就要采用深拷贝等操作了。在这里，对于数组的过滤，我们可以巧妙地使用字符串比较的方法来判断数组元素是否相等，前提是数组元素需要实现排好序。

---

如果以上有什么错误，欢迎轻拍。

Answer 4

数学上叫整数拆分，请参考百度百科