Need help with the GENERATING SUBSETS code

void search(int k) {
  if (k == n) {
    // process subset
  } else {

I am having a really hard time understand this code. I especially don’t understand how ‘k’ turns to 2 after ‘k’ reaches 3. I don’t understand because there’s no such code that does search(k-1) but it backtracks automatically. I think It’s related to the thing backtracking. Someone plz help!!!

This is a recursive function. When search is called within itself, the previous function call’s state is preserved. Suppose search(0) is called with n = 2. Then, the call stack will look something like this:

search(0) --> search(1) --> search(2)

At this point, however, it will go into the base case k == n, and the function will not make further recursive calls; instead, it will end the function, and go back to the call where it originally was:

search(0) --> search(1)

Since the state of each previous call is preserved, it will simply go back to search(1) rather than ending all active function calls. To see how this actually generates the subsets, try working it out by hand for a small n – it comes down to the function generating all subsets once with k and once without k, for each k.