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)