I am new to Backtracking, and I was solving 78. Subsets on Leetcode. After, debugging this solution I found that when we reach let's say index = 3 in array like [1, 2, 3] we decrement it again when we hit return statment in the if condition. However, I don't really understand how did this happen ?
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
def dfs(index):
if(index >= len(nums)):
res.append(subset.copy())
return
subset.append(nums[index])
dfs(index + 1)
subset.pop()
dfs(index + 1)
dfs(0)
return res
and how we jump from appending the nums[index] in the subset to poping the numbers from it ? I don't really grasb it even after debugging it
**The Question ** 78. Subsets
Given an integer array nums of unique elements, return all possible subsets
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
The key in understanding the backtracking to "previous" index values, is that each execution of dfs has its own index name. This name is not to be confused with the index of the caller. Although both the caller and the "callee" use the same name, these can have different values. Note how the caller passes index + 1 to the recursive call, but does not really update its own index; it merely tells the called function to initialise their index with one more.
This means that when that recursive call finishes, their index reaches its end-of-life, and the caller continues with its own index, which didn't change. This may give the impression that a value is being decreased, but that is not actually what happens.
Incidentally, the local index represents the current depth of the recursion.