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