Recursive code gives wrong answer in Javascript-CodePudding

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

CodePudding user response：

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
     
    
}

CodePudding user response：

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