I've been working on learning backtracking and I know how the general template goes, but I'm struggling to fully understand how the algorithm backtracks, specifically how it knows when to pop from a current solution and how often to.

I know it should be that we have a base case, and when we hit this base case, we then return from this current iteration. But then I'm not fully sure on why we pop from a solution many times until we start exploring again.

For example, I've been working on the classic "Generate Parentheses" problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

E.g.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Here's my working solution after applying my existing knowledge of how the template should be, but I just can't work out how currCombo.pop() falls into the thinking and visualising how it works.

function generateParenthesis(n) {
    const result = [];
    backtrack(result, n, 0, 0, []);
    return result;
};

function backtrack(result, n, open, close, currCombo) {
    if (currCombo.length === 2 * n) {
        result.push(currCombo.join(''));
        return;
    }

    if (open < n) {
        currCombo.push('(');
        backtrack(result, n, open   1, close, currCombo);
        currCombo.pop();
    }
    if (close < open) {
        currCombo.push(')');
        backtrack(result, n, open, close   1, currCombo);
        currCombo.pop();
    }
}

So for example, the algorithm first outputs: "((()))" And the second result is then: "(()())"

But how does the algorithm know it needs to pop off 3 close brackets and then 1 open bracket, and then to continue adding brackets from there? I debugged the code line by line and just couldn't see why it would do a certain number of pop operations and then continue.

I've tried checking out Youtube videos, articles, blogs, but I just can't visualise what the algorithm is doing and how it's making the decisions that it is when it is.

Any help much appreciated. Thanks

CodePudding user response：

There's nothing for the algorithm to "know" exactly; each pop is an undo of the push that set up the call frame for the recursion. That's it. Most of the logic has to do with your if statements that protect the recursion, ensuring balance.

Think of it as a depth-first graph exploration where each node is a possible arrangement of up to n ( parentheses and n ) parentheses. The open and close variables don't encode any unique information. These variables are conveniences to avoid each frame having to count the already-chosen parentheses, and having these counts enables you to avoid exporing pointless subtrees which can never produce a result, like (((( on n=3.

Each recursive call frame begins by asking whether it's at a result point. If so, save the result and return. If not, if it'd be possible to reach a result by adding a ( to the end of the string so far, explore that subtree, then undo the move by popping, resetting to a clean state. Next, try adding ) if that might lead to a result, explore the subtree, and undo the move. After undoing any modifications made and exploring one or both subtrees, return to the caller since all possibilities have been explored rooted at this node in the graph.

Let's trace how we get to the first result "((()))" and then to "(()())".

On the first call, open < n ("the first branch") is true, so we push ( and spawn one recursive call with open = 1. This initial ( stays in the result for the duration of the algorithm; close < open ("the second branch") is false for the first call frame.

On the second call, both branches are true, so we'll eventually make two recursive calls, but for starters we try pushing ( again to give the string (( and recursing with open = 2.

On the third call, both branches are true, so we'll eventually make two recursive calls, but for starters we try pushing ( again to give the string ((( and recursing with open = 3.

On the fourth call, the first branch is false, so we only perform one recursion from the second branch close < open with the string ((() and open = 3, close = 1.

On the fifth call, the first branch is false, so we only perform one recursion from the second branch close < open with the string ((()) and open = 3, close = 2.

On the sixth call, the first branch is false, so we only perform one recursion from the second branch close < open with the string ((())) and open = 3, close = 3.

On the seventh call, currCombo.length === 2 * n is true so we add ((())) to the result and return back up one call frame.

Now the sixth call resumes executing and there's no code left to run; recall that for this frame, the first branch was false, so we skipped it, and we've already explored the second branch recursively. Pop the string to ((()) and return to the caller.

Now the fifth call resumes executing and there's no code left to run; recall that for this frame, the first branch was false, so we skipped it, and we've already explored the second branch recursively. Pop the string to ((() and return to the caller.

Now the fourth call resumes executing and there's no code left to run; recall that for this frame, the first branch was false, so we skipped it, and we've already explored the second branch recursively. Pop the string to ((( and return to the caller.

Now the third call resumes executing but we haven't explored the second branch yet, so pop ( again to give the string ((, then push ) and recurse on (() and open = 2, close = 1.

A new call, the eighth call, begins, and both branches are true, so we'll eventually make two recursive calls, but for starters we try pushing ( again to give the string (()( and recursing with open = 3, close = 1.

A new call, the ninth call, begins. The first branch is false, so we only perform one recursion from the second branch close < open with the string (()() and open = 3, close = 2.

A new call, the tenth call, begins. The first branch is false, so we only perform one recursion from the second branch close < open with the string (()()) and open = 3, close = 3.

A new call, the eleventh call, begins. On this call, currCombo.length === 2 * n is true so we add (()()) to the result and return back up one call frame.

Now the tenth call resumes executing and there's no code left to run; recall that for this frame, the first branch was false, so we skipped it, and we've already explored the second branch recursively. Pop the string to (()() and return to the caller.

Now the ninth call resumes executing and there's no code left to run; recall that for this frame, the first branch was false, so we skipped it, and we've already explored the second branch recursively. Pop the string to (()( and return to the caller.

Now the eighth call resumes executing but we haven't explored the second branch yet, so pop ( again to give the string ((), then push ) and recurse on (()) and open = 2, close = 2.

... I'll stop here; finish tracing the execution to the next result (())() which you can see we're well on our way to building.

But how does the algorithm know it needs to pop off 3 close brackets and then 1 open bracket, and then to continue adding brackets from there?

It popped off 3 close parens because there was nothing left to explore on those call frames. The first branch was false and the second branch had already been explored.

The reason the 1 open paren was popped next is because the recursive subtree of possibilities starting with the open paren had already been explored fully, but the subtree rooted with ) hadn't been explored yet. When we left off our algorithm trace, we were just launching into exploring that subtree. When the subtree is exhausted and any results that it ultimately yielded had been stored, that paren would also pop off and the frame would be completely explored.

At that point, its caller (the second call in the above example) would still need to explore the subtree starting with (), open = 1, close = 1, since it had only tried ((, open = 2, close = 0 up to that point. In other words, it'll have explored the ( branch but not the ) branch that will ultimately lead to the last result ()()().

Here's a visualization of the recursive call tree:

function generateParenthesis(n) {
  const result = [];
  backtrack(result, n, 0, 0, []);
  return result;
};

function backtrack(result, n, open, close, currCombo, depth=0) {
  console.log(`${" ".repeat(depth * 2)}enter '${currCombo.join("")}'`);

  if (currCombo.length === 2 * n) {
    result.push(currCombo.join(''));
    console.log(`${" ".repeat(depth * 2)}result '${currCombo.join("")}'`);
    console.log(`${" ".repeat(depth * 2)}exit  '${currCombo.join("")}'`);
    return;
  }

  if (open < n) {
    currCombo.push('(');
    backtrack(result, n, open   1, close, currCombo, depth   1);
    currCombo.pop();
  }
  if (close < open) {
    currCombo.push(')');
    backtrack(result, n, open, close   1, currCombo, depth   1);
    currCombo.pop();
  }

  console.log(`${" ".repeat(depth * 2)}exit  '${currCombo.join("")}'`);
}

generateParenthesis(3);

If that's too complex, you can dial it back to n = 2, trace that, then do n = 3.