List all the ways that 1, 2, and 3 can add up to 4, the order matters. For example, [1, 1, 1, 1] is one way. [1,1,2] is different from [1,2,1]

I have figured out one way it works on paper. But I still cannot write the code for it. Please help and Please check out this picture of My Idea for clarity.

This code I wrote failed. But this is how far I've got.

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

As I console.log('sum', sum, 'step', cur), I get the desired results:

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

My problem is that I don't know how to push the result to results array. It should look like [[1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], and on]

CodePudding user response：

Some issues:

• Although the array returned by the recursive call is captured in the variable c, that variable is not used further on, and so it has been useless.

• results is initialised as [], but is then never modified/extended, so the final return result is guaranteed to return that empty list.

• The above two issues need to be solved by iterating the solutions present in c: append the current value to those solutions (since we had subtracted that value to get those solutions), and append those extended solutions to the current results array.

• When remaining is equal to 0, it makes no sense to make more recursive calls. This is actually a base case of the recursion. (I prefer to do this check one level deeper in the recursion, at the start of the function: if the sum is 0, we should return an empty solution which can then be extended by the selected values as we get back out of recursion).

• Unrelated, but it is better practice to separate your statements with semicolons. You wouldn't be the first to fall in one of the traps of automatic semicolon insertion. Better take control.

Here is a corrected version:

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

CodePudding user response：

This is a perfect opportunitiy to use backtracking. The idea of backracking is that we set out to try all possible combinations, but when our current combination fails and we can't continue building upon it, then we go back and try something else.

The way we approach a backtracking problem is this:

1. Figure out how we can break our answer into parts or steps
   • So for this problem, as you already did, we break the solution into an array.
   • We'll consider each value in the array a step in building our solution.
2. Figure out a way to find all the possible solutions at each step
   • For this question, the possible solutions are the values in the input array [1,2,3]
3. Set up a loop that'll try all the solutions
   • The reason I said set up, is because even though we'll start the first iteration, the idea isn't to directly iterate all the solutions at our current step.
   • We'll be trying to build our solution with our current step as a part of that solution
4. Start at the first possible solution step:
   • Add it to your solution array
   • Check if its possible to continue building the solution
     • In this question, if the sum of our steps is larger than 4, we can't keep building.
   • If it's possible, recurse, with our current solution as the starting point
     • Repeat Steps 3 - 4
   • If it's not possible to keep building, remove the current step from the solution, and now we can iterate the loop to try the next possible solution at the current step.
5. Each time we recurse, we check if our solution solves our main input, and if it does we add it to an array.

That's a lot of words, let's solve the question:

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