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

177
Visualizações
Recursive code gives wrong answer in Javascript

I want to print all subsets of an array using backtracking in Javascript my algorithm is right but it gives some unexpected answers. I think this is related to javascript language.

// this is base function where i am calling recursive function .
function solveIt(A,B,C,D,E){
      let ans = [];   // this is ans array
      let sub = [];    // this is subset array 
      printAllSubset(A,0,sub,ans); // Calling the helper function
      return ans;    // returing anser
       
    
}
// My recursive code 
function printAllSubset(nums,idx,sub,ans){
    
    if(idx==nums.length){.   // This is base condition
        ans.push(sub);
       
        return ans;
        
    }
    // include current index
    sub.push(nums[idx]);            // including the current index
    printAllSubset(nums,idx+1,sub,ans);  // recuring for all possible sub problem
    
    // exclude current index
    
    sub.pop();                            // excluding the current index
    printAllSubset(nums,idx+1,sub,ans);   // recuring for all possible scenerio
     
    
}
const A=[1,2,3];
const res = solveIt(A,B,C);

console.log(res)

// output I am getting - 
[
  [], [], [], [],
  [], [], [], []
]

// But the expected output should be - 

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]



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

0

The problem here is that you are adding the same sub array to ans and any changes to sub reflect inside ans data as well. So you'll need add a copy of sub instead:

const A=[1,2,3];
const res = solveIt(A);

console.log(res)

// this is base function where i am calling recursive function .
function solveIt(A,B,C,D,E){
      let ans = [];   // this is ans array
      let sub = [];    // this is subset array 
      printAllSubset(A,0,sub,ans); // Calling the helper function
      return ans;    // returing anser
       
    
}
// My recursive code 
function printAllSubset(nums,idx,sub,ans){
    
    if(idx==nums.length){   // This is base condition
        ans.push([...sub]); // push a copy of the array
       
        return ans;
        
    }
    // include current index
    sub.push(nums[idx]);            // including the current index
    printAllSubset(nums,idx+1,sub,ans);  // recuring for all possible sub problem
    
    // exclude current index
    
    sub.pop();                            // excluding the current index
    printAllSubset(nums,idx+1,sub,ans);   // recuring for all possible scenerio
     
    
}

about 4 years ago · Juan Pablo Isaza Relatório

0

You build towards having the answer in ans but then throw it away. One answer is to make ans a global variable and remove it from recursive function calls:

let ans=[]
function solveIt(A){ 
      printAllSubset(A,0,[]); // Calling the helper function
}

function printAllSubset(nums,idx,sub){

    if(idx===nums.length){.   // This is base condition
        ans.push(sub);
    }
    // include current index
    sub.push(nums[idx]);            // including the     current index
    printAllSubset(nums,idx+1,sub);  // recuring for all possible sub problem

    // exclude current index

    sub.pop();                            // excluding the current index
    printAllSubset(nums,idx+1,sub);   // recuring for all possible scenerio
}

The other is to catch the return of the recursive calls to printAllSubset:

function solveIt(A){ 
      return printAllSubset(A,0,[],[]); // Calling the helper function
}

function printAllSubset(nums,idx,sub,ans){

    if(idx===nums.length){.   // This is base condition
        ans.push(sub);
   
        return ans;
    
    }
    // include current index
    sub.push(nums[idx]);            // including the     current index
    ans=printAllSubset(nums,idx+1,sub,ans);  // recuring for all possible sub problem

    // exclude current index

    sub.pop();                            // excluding the current index
    ans=printAllSubset(nums,idx+1,sub,ans);   // recuring for all possible scenerio

    return ans;
}
about 4 years ago · Juan Pablo Isaza Relatório

0

The other answers here show what was wrong with your code and how to fix it. I would just like to demonstrate a cleaner recursive way to write this:

const powerset = ([x, ...xs] = []) =>
  x == undefined
    ? [[]]
    : powerset (xs) .flatMap (ys => [ys, [x, ...ys]])

console .log (JSON .stringify (powerset ([1, 2, 3])))

As with all recursion, one useful way to think about this is to recognize that it works for a base case, and if every recursive call make progress toward a base case, and if we can see that when it works for our recursive call it also works for our current call, then we can be assured that it works for all cases. Because powerset ([]) //=> [[]], it works for a base case. Because every recursive call involves shrinking our input array by one, then our second condition holds; we'll eventually reach a base case. The third condition we show by example: we assume that powerset ([2, 3]) properly yields [[], [2], [3], [2, 3]], then powerset ([1, 2, 3]) will yield

[[], [2], [3], [2, 3]] .flatMap (ys => [ys, [1, ...ys]])

which is the same as

[... [[], [1]], ... [[2], [1, 2]], ... [[3], [1, 3]], ... [[2, 3], [1, 2, 3]]]
//    `--[]--'      `----[2]----'       `----[3]----'     `------[2, 3]------'

which is simply

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

and so the recursive case works properly. It's not hard to actually prove that all the subsets will show up with this technique. We would just formalize the example above.

But this means that this function will accurately capture the powerset of a set expressed as a JS array.

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