Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

201
Visualizações
Javascript 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

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]

about 4 years ago · Juan Pablo Isaza
2 Respostas
Responde à pergunta

0

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

about 4 years ago · Juan Pablo Isaza Relatório

0

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

about 4 years ago · Juan Pablo Isaza Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda