So I am trying to solve a problem in recursion and backtracking using js as my language. the question is :
` Subsets ( Backtracking Algorithm using Recursion )
// Given an integer array nums of unique elements, return all possible subsets (the power set).
// The solution set must not contain duplicate subsets. Return the solution in any order.
// Input: [1,2,3] ----->>>>> Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// Input: [0] ----->>>>> Output: [[],[0]]`
My Solution
function subsets(prob) {
let result = [];
let temp = [];
function getPowSet(nums, i) {
if (i === nums.length) {
return result.push([...temp]);
}
console.log(temp, i, "0");
temp.push(nums[i]);
getPowSet(nums, i + 1);
console.log(temp, i, "1");
temp.pop();
getPowSet(nums, i + 1);
console.log(temp, i, "2");
}
getPowSet(prob, 0);
return result;
}
and I have put certain logs in the code to understand the flow
the logs looks like:-
[ 1 ] 0 0
[ 1, 2 ] 1 0
[ 1, 2, 3 ] 2 0
[ 1, 2 ] 2 1
[ 1, 2 ] 2 2
[ 1 ] 1 1
[ 1, 3 ] 2 0
[ 1 ] 2 1
[ 1 ] 2 2
[ 1 ] 1 2
[] 0 1
[ 2 ] 1 0
[ 2, 3 ] 2 0
[ 2 ] 2 1
[ 2 ] 2 2
[] 1 1
[ 3 ] 2 0
[] 2 1
[] 2 2
[] 1 2
[] 0 2
My concern:
So when the code completes its 1st recursion loop and hits the base case when i become 3 and pushes the temp array to result and returns.. why does the i still logs as 2 in the next log, because there is no i-- going on anywhere inside the base case so it should still log i = 3
here :-
[ 1 ] 0 0
[ 1, 2 ] 1 0
[ 1, 2, 3 ] 2 0
[ 1, 2 ] 2 1 <--------
Top comments (0)