Javascript列出了1、2、3加起来等于4的所有方式，顺序很重要。例如，[1，1，1，1]是一种方式

Question

列出1、2和3相加为4的所有方式，顺序很重要。例如，[1，1，1,1]是一种方法<代码>[1,1,2]与[1,2,1]不同

我已经想出了一个理论上可行的方法。但是我仍然不能为它写代码。请帮助，请检查我的想法清晰的图片。

我写的这个代码失败了。但这就是我已经走了多远。

function theseAddToSum(steps = [], sum) {
  let results = [];

  if (steps.length < 1) return 'error'

  for (let i = 0; i < steps.length; i++) {
    let cur = steps[i];
    let remaining = sum - cur; 

    if (remaining >= 0) {
      console.log('sum', sum, 'step', cur)
      let c = theseAddToSum(steps, remaining)
    }
  }

  return results
}
console.log(theseAddToSum([1, 2, 3], 4))

当我console.log（'sum'， sum，'Step'， cur）时，我得到了想要的结果：

sum 4 step 1
sum 3 step 1
sum 2 step 1
sum 1 step 1
sum 2 step 2
sum 3 step 2
sum 1 step 1
sum 3 step 3
sum 4 step 2
sum 2 step 1
sum 1 step 1
sum 2 step 2
sum 4 step 3
sum 1 step 1

我的问题是，我不知道如何将结果推送到结果数组。它应该看起来像[[1,1,1，1]、[1,2,2]、[2,1]、[1,3]、[3,1,2]等等]

Answer 1

这是使用回溯的绝佳机会。回溯的想法是，我们开始尝试所有可能的组合，但当我们当前的组合失败了，我们不能继续在它的基础上建立，然后我们回去尝试别的东西。

我们处理回溯问题的方式如下：

• 找出我们如何将答案分解为部分或步骤
  • 因此，对于这个问题，就像您已经做的那样，我们将解决方案分解为一个数组。
  • 我们将数组中的每个值视为构建解决方案的一个步骤。
  < li >对于此问题，可能的解决方案是输入数组< code>[1，2，3]中的值
  • 我说设置的原因是因为即使我们将开始第一次迭代，我们的想法也不是直接迭代当前步骤中的所有解决方案。
  • 我们将尝试使用当前步骤构建解决方案，作为解决方案的一部分
  < li >将其添加到您的< code >解决方案阵列中 < li >检查是否可以继续构建解决方案 < ul > < li >在这个问题中，如果我们的步骤之和大于4，我们就不能继续构建。
  • 重复步骤3-4

  话真多，我们来解决问题:

  const getSum = (arr) => arr.reduce((acc, num) => num + acc, 0);
  
  function theseAddToSum(steps, sum) {
    const solutions = [];
    function recurse(steps, sum, currentSol) {
      if (getSum(currentSol) === sum) { 
        solutions.push([...currentSol]); 
        return
      }
      for (let i = 0; i < steps.length; i++) {
        currentSol.push(steps[i]);
        if (getSum(currentSol) <= sum) {
          recurse(steps, sum, currentSol);
        }
        currentSol.pop(); 
      }
    }
    recurse(steps, sum, [])
    return solutions;
  }
  
  console.log(theseAddToSum([1, 2, 3], 4));

Answer 2

一些问题：

>

尽管递归调用返回的数组被捕获在变量c中，但该变量没有进一步使用，因此它一直没有用。

结果被初始化为[]，但随后从未被修改/扩展，因此最终的返回结果保证返回该空列表。

以上两个问题需要通过迭代< code>c中的解决方案来解决:将当前值追加到那些解决方案中(因为我们已经减去了那个值以获得那些解决方案)，并将那些扩展的解决方案追加到当前的< code>results数组中。

当< code>remaining等于0时，进行更多的递归调用是没有意义的。这实际上是递归的一个基本情况。(我更喜欢在递归的更深一层，在函数的开始进行这种检查:如果和是0，我们应该返回一个空解，然后当我们从递归中返回时，可以用选择的值扩展这个空解)。

无关，但最好用分号分隔你的语句。你不会是第一个落入自动分号插入陷阱的人。最好掌握控制权。

以下是更正后的版本：

js lang-js prettyprint-override">function theseAddToSum(steps = [], sum) {
    // Base cases:
    if (sum < 0) return []; // No solutions
    if (sum == 0) return [[]]; // A solution

    let results = [];
    if (steps.length < 1) return 'error';

    for (let i = 0; i < steps.length; i++) {
        let cur = steps[i];
        let remaining = sum - cur; 
        let c = theseAddToSum(steps, remaining)
        // Use the solutions we got back from recursion
        for (let solution of c) {
            solution.push(cur); // ... then extend them
            results.push(solution); // ... and collect them
        }
    }        
    return results;
}

console.log(theseAddToSum([1, 2, 3], 4));