Search code examples
javabacktracking

Approaches to understand backtracking better

i wanted to ask what helped you grasp the concept of backtracking better.

I think i understand the idea behind it and recursion well enough, yet, i struggle to make sense of why backtracking leads to the wanted outcome. I tried to "dry run" the code on paper, and understand the program flow better, but to almost no avail.

So, naturally, i have a extremely hard time to come up with my own backtracking solutions.

I think i understand why the base case makes sense, why the if-calls are necessary, and see that every option is being checked (by using a debugger), yet i do not see why java computes the code that way internally.

For example here: https://codingbat.com/prob/p145416:

java 

**
  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);
  
  // Key idea: nums[start] is chosen or it is not.
  // Deal with nums[start], letting recursion
  // deal with all the rest of the array.
  
  // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  
  // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;
  
  // If neither of the above worked, it's not possible

  System.out.println("test"); // Why does it reach that point?
  return false;
}
**
Solution

  • i wanted to ask what helped you grasp the concept of backtracking better.

    For grasping the general idea, it helped me to watch visualisations of solutions using backtracking (videos or pages with visualisations). For grasping how the calls and recursive calls work, I just did a lot of step through debugging and watched some visualisations as well.

    From the comments that you added to your code, I can see, that you already grasped the general idea of backtracking and why those conditions and recursive calls are there.

    So how do computers (this is not specific to Java) perform calls and recursive calls and more importantly, how do they keep track of where to return after a call finishes executing?

    They use a call stack. From wikipedia

    A call stack is used for several related purposes, but the main reason for having one is to keep track of the point to which each active subroutine should return control when it finishes executing. An active subroutine is one that has been called, but is yet to complete execution, after which control should be handed back to the point of call. Such activations of subroutines may be nested to any level (recursive as a special case), hence the stack structure.

    A call stack keeps track of calls that are still in progress by pushing (adding) stack frames on the stack every time a call happens and popping (removing) them when an active call returns.

    The stack frames contain information about (simplified):

    1. the values of the parameters of the call
    2. the return address = the position in code to return to after the call finishes executing
    3. the local variables of the called method, the context/scope

    The stack and the stack frames make recursion calls possible.

    I know that you already used a debugger to step through the code while it was executing, but let's do it again here on "paper".

    I will use line numbers in your code (I also removed the comments) to make it easier to reference the lines. The method that will be called recursively has 5 lines of code.

       boolean groupSum(int start, int[] nums, int target) {

1:   if (start >= nums.length) return (target == 0); 

2:   if (groupSum(start + 1, nums, target - nums[start])) return true;

3:   if (groupSum(start + 1, nums, target)) return true;

4:   System.out.println("test"); // Why does it reach that point?

5:   return false;

   }

    Let's take the call to groupSum(0, [2, 4, 8], 9) as an example.

    When some part of your code calls groupSum(0, [2, 4, 8], 9) it will push this call on the call stack (create a stack frame) and start executing the method body.

    Stack frame 1 created: groupSum(0, [2, 4, 8], 9)
Parameters: start = 0, target = 9, nums = [2, 4, 8]

// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(0 + 1, [2, 4, 8], 9 - 2)
// which pushes a new stack frame on the call stack

Stack frame 2 created: groupSum(1, [2, 4, 8], 7)
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// This creates a local scope (context) for frame 2.
// Frame 1 is isolated from changes to variables in Frame 2

// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(1 + 1, [2, 4, 8], 7 - 4)
// which pushes a new stack frame on the call stack

Stack frame 3 created: groupSum(2, [2, 4, 8], 3)
Parameters: start = 2, target = 3, nums = [2, 4, 8]

// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(2 + 1, [2, 4, 8], 3 - 8)
// which pushes a new stack frame on the call stack

Stack frame 4 created: groupSum(3, [2, 4, 8], -5)
Parameters: start = 3, target = -5, nums = [2, 4, 8]

// Line 1 condition is true. So the method returns (-5 == 0),
// which means it returns false.

    This is where the actual backtracking happens for the first time. It has reached the end of the array, but it has not found a valid solution, since -5 is not 0, so it returns and goes back in the call stack - it backtracks.

    A return statement pops a frame from the call stack and continues the code execution at the return address - at the point in code that invoked the method that we are now returning from.

    In this case, it pops Frame 4, restores the local scope for Frame 3 (all the values of the local variables are restored) and the execution continues on line 2 (of Frame 3). This makes the backtracking "work", since it restores the previous state of the local scope at the call site and then continues the execution from there.

    Stack frame 3 restored:
Parameters: start = 2, target = 3, nums = [2, 4, 8]

// Line 2 condition is false (because false was returned) so it keeps going
// Line 3 calls groupSum(2 + 1, [2, 4, 8], 3)
// which pushes a new stack frame on the call stack

Stack frame 4 created: // this is a completely new frame 4,
// has no relation to frame 4 from before
Parameters: start = 3, target = 3, nums = [2, 4, 8]

// Line 1 condition is true, it returns (3 == 0), so it returns false.

    Here it backtracks again. This pops a frame from the call stack again, so Frame 3's scope is restored, but this time it continues the execution on line 3

    Stack frame 3 restored:
Parameters: start = 2, target = 3, nums = [2, 4, 8]

// Line 3 condition is false (because false was returned) so it keeps going
// Line 4 prints out "test". This is when and how this line is executed.
// Line 5 returns false.

    Here it backtracks as well, because both call paths (calls from line 2 and line 3), have not found a solution from the current state and both had to backtrack.

    This pops a frame from the call stack, so frame 2's scope is restored, it continues on line 2.

    Stack frame 2 restored:
Parameters: start = 1, target = 7, nums = [2, 4, 8]

// Line 2 condition is false (because false was returned), so it keeps going
// Line 3 calls groupSum(1 + 1, [2, 4, 8], 7)
// which pushes a new stack frame on the call stack

    Stack frame 3 is created and the whole thing repeats, with slightly different numbers for frame 4's target 7 - 8 = -1 and then 7, but with the same outcomes (false returned, so backtracking).

    It prints "test" again in frame 4 line 4 and returns false on line 5

    Then frame 3 line 4 prints "test" and returns false on line 5 (backtracks) and frame 2 is restored again on line 3

    Stack frame 2 restored:
Parameters: start = 1, target = 7, nums = [2, 4, 8]

// Line 3 condition is false (because false was returned) so it keeps going
// Line 4 prints "test"
// Line 5 returns false (backtracks)

Stack frame 1 restored:
Parameters: start = 0, target = 9, nums = [2, 4, 8]

// Line 2 condition is false, so it keeps going
// Line 3 repeats the whole thing with frames 2, 3 and 4,
// outcomes are still false (backtracks a few times),
// so after a few more "test" are printed, frame 1 is restored again,
// but this time on line 3 and since the returned value is false,
// the condition is false, so it keeps going
// Line 4 prints "test
// Line 5 returns false (backtracks)

    At this point the frame 1 is popped from the call stack and the execution is retuned to the original caller of the method groupSum(0, [2, 4, 8], 9), so we could say that the "Root Frame" (Frame 0) is restored and the value false is retuned to the original caller.

    The result of the whole execution is false, which is expected, since there is no group sum in 2, 4, 8 that adds to 9.

    EDIT: Here is another tip that might come in handy (maybe when you will be coming up with backtracking algorithms). In (Java) IDEs, when the debugger stops on a breakpoint, you can also see the frames of the current call stack in the debugger window and the values for variables in the current scope. You can also select other frames and see where the calls started and the values for variables in that frame's scope. Some IDEs even show the local variables inline in code (as can be seen in the image below).

    Here is an example from IDEA Community Edition Call stack frames of a recursive call