Backtracking Algorithm Practice: Generating Valid Parentheses

括号问题可以简单分成两类，一类是前文写过的 括号的合法性判断 ，一类是合法括号的生成。对于括号合法性的判断，主要是借助「栈」这种数据结构，而对于括号的生成，一般都要利用 回溯算法 进行暴力穷举。

回到正题，看下力扣第 22 题「括号生成」，要求如下：

请你写一个算法，输入是一个正整数 n，输出是 n 对儿括号的所有合法组合，函数签名如下：

List<String> generateParenthesis(int n);

vector<string> generateParenthesis(int n);

def generateParenthesis(n: int) -> List[str]:

func generateParenthesis(n int) []string

var generateParenthesis = function(n) {};

比如说，输入 n=3，输出为如下 5 个字符串：

"((()))",
"(()())",
"(())()",
"()(())",
"()()()"

有关括号问题，你只要记住以下性质，思路就很容易想出来：

1、一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。

2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

如果不跟你说这个性质，可能不太容易发现，但是稍微想一下，其实很容易理解，因为从左往右算的话，肯定是左括号多嘛，到最后左右括号数量相等，说明这个括号组合是合法的。

反之，比如这个括号组合 ))((，前几个子串都是右括号多于左括号，显然不是合法的括号组合。

下面就来手把手实践一下回溯算法框架。

回溯思路

明白了合法括号的性质，如何把这道题和回溯算法扯上关系呢？

算法输入一个整数 n，让你计算 n 对儿括号能组成几种合法的括号组合，可以改写成如下问题：

现在有 2n 个位置，每个位置可以放置字符 ( 或者 )，组成的所有括号组合中，有多少个是合法的？

这个命题和题目的意思完全是一样的对吧，那么我们先想想如何得到全部 2^(2n) 种组合，然后再根据我们刚才总结出的合法括号组合的性质筛选出合法的组合，不就完事儿了？

如何得到所有的组合呢？这就是标准的暴力穷举回溯框架啊，我们前文 回溯算法套路框架详解 都总结过了：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

那么对于我们的需求，如何打印所有括号组合呢？套一下框架就出来了，伪码如下：

LinkedList<String> track;
void backtrack(int n, int i) {
    // i represents the current position, there are a total of 2n positions
    // having exhausted all positions, we get a combination of length 2n
    if (i == 2 * n) {
        print(track);
        return;
    }

    // for each position, there are two choices: left parenthesis or right parenthesis
    for choice in ["(", ")"] {
        // make a choice
        track.push(choice);
        // enumerate the next position
        backtrack(n, i + 1);
        // undo the choice
        track.pop(choice);
    }
}

#include <string>
#include <vector>
#include <iostream>

std::vector<std::string> track;

void print(const std::vector<std::string>& v) {
    for (const std::string& s : v) {
        std::cout << s;
    }
    std::cout << std::endl;
}

void backtrack(int n, int i) {
    // i represents the current position, there are a total of 2n positions
    // have exhausted all positions to the end, obtained a combination of length 2n
    if (i == 2 * n) {
        print(track);
        return;
    }

    // for each position, there are two choices: left parenthesis or right parenthesis
    for (std::string choice : {"(", ")"}) {
        // make a choice
        track.push_back(choice);

        // enumerate the next position
        backtrack(n, i + 1); 

        // undo the choice
        track.pop_back();
    }
}

track = []
def backtrack(n, i):
    # i represents the current position, with a total of 2n positions
    # having exhausted all positions, we get a combination of length 2n
    if i == 2 * n:
        print(track)
        return
    
    # for each position, there are two choices: left parenthesis or right parenthesis
    for choice in ["(", ")"]:
        # make a choice
        track.append(choice)
        # exhaustive the next position
        backtrack(n, i + 1)
        # undo the choice
        track.pop()

import (
	"fmt"
	"strings"
)

var track []string

func backtrack(n int, i int) {
	// i represents the current position, there are a total of 2n positions
	// exhausted all positions to the end, obtained a combination of length 2n
	if i == 2*n {
		fmt.Println(strings.Join(track, ""))
		return
	}

	// for each position, there are two choices: left parenthesis or right parenthesis
	for _, choice := range []string{"(", ")"} {
		// make a choice
		track = append(track, choice)
		// enumerate the next position
		backtrack(n, i+1)
		// undo the choice
		track = track[:len(track)-1]
	}
}

var track = new Array();
var backtrack = function(n, i) {
    // i represents the current position, with a total of 2n positions
    // the enumeration has reached the last position, obtaining a combination of length 2n
    if (i == 2 * n) {
        console.log(track);
        return;
    }

    // for each position, there are two choices: left parenthesis or right parenthesis
    for (var choice of ["(", ")"]) {
        // make a choice
        track.push(choice);
        // enumerate the next position
        backtrack(n, i + 1);
        // undo the choice
        track.pop();
    }
}

Now that we can print all bracket combinations, how do we filter out the valid ones? It's simple; just add a few conditions to "prune" the invalid combinations.

For 2n positions, there must be n left brackets and n right brackets. Instead of simply recording the exhaustive position i, we use left to keep track of how many left brackets we can still use, and right to keep track of how many right brackets we can still use. This way, we can filter based on the rules for valid brackets we just summarized:

class Solution {
    // the path during backtracking
    StringBuilder track = new StringBuilder();
    // record all valid parenthesis combinations
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        if (n == 0) return res;
        // initialize the number of available left and right parentheses to n
        backtrack(n, n);
        return res;
    }

    // the number of available left parentheses is left, and the number of available right parentheses is right
    private void backtrack(int left, int right) {
        // if there are more left parentheses left, it is not valid
        if (right < left) return;
        // a count less than 0 is definitely not valid
        if (left < 0 || right < 0) return;
        // when all parentheses are used up, a valid parenthesis combination is obtained
        if (left == 0 && right == 0) {
            res.add(track.toString());
            return;
        }

        // make a choice, try to put a left parenthesis
        track.append('(');
        backtrack(left - 1, right);
        // cancel the choice
        track.deleteCharAt(track.length() - 1);

        // make a choice, try to put a right parenthesis
        track.append(')');
        backtrack(left, right - 1);
        // cancel the choice
        track.deleteCharAt(track.length() - 1);
    }
}

class Solution {
private:
    // the path during backtracking
    string track = "";
    // record all valid parenthesis combinations
    vector<string> res; 
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) return res;
        // initialize the number of available left and right parentheses to n
        backtrack(n, n);
        return res;
    }

    // the number of available left parentheses is left, and the right is right
    void backtrack(int left, int right) {
        // if there are more left parentheses left, it's not valid
        if (right < left) return;
        // a count less than 0 is definitely not valid
        if (left < 0 || right < 0) return;
        // when all parentheses are used up, a valid parenthesis combination is obtained
        if (left == 0 && right == 0) {
            res.push_back(track);
            return;
        }

        // make a choice, try to put a left parenthesis
        track.push_back('(');
        backtrack(left - 1, right);
        // undo the choice
        track.pop_back();

        // make a choice, try to put a right parenthesis
        track.push_back(')');
        backtrack(left, right - 1);
        // undo the choice
        track.pop_back();
    }
};

class Solution:
    def __init__(self):
        # the path during backtracking
        self.track = ''
        # record all valid parenthesis combinations
        self.res = []

    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0: return self.res
        # initialize the number of available left and right parentheses to n
        self.backtrack(n, n)
        return self.res

    # the number of available left parentheses is left, and the right is right
    def backtrack(self, left: int, right: int) -> None:
        # if there are more left parentheses left, it is not valid
        if right < left: return
        # a count less than 0 is definitely not valid
        if left < 0 or right < 0: return
        # when all parentheses are used up, a valid parenthesis combination is obtained
        if left == 0 and right == 0: 
            self.res.append(self.track)
            return

        # make a choice, try to put a left parenthesis
        self.track += '('
        self.backtrack(left - 1, right)
        # cancel the choice
        self.track = self.track[:-1]

        # make a choice, try to put a right parenthesis
        self.track += ')'
        self.backtrack(left, right - 1)
        # cancel the choice
        self.track = self.track[:-1]

func generateParenthesis(n int) []string {
    var track string
    var res []string

    var backtrack func(left, right int)
    backtrack = func(left, right int) {
        // if there are more left parentheses left, it's illegal
        if right < left {
            return
        }
        // if the count is less than 0, it's definitely illegal
        if left < 0 || right < 0 {
            return
        }
        // when all parentheses are used up, we get a valid parenthesis combination
        if left == 0 && right == 0 {
            res = append(res, track)
            return
        }

        // make a choice, try to put a left parenthesis
        track += "("
        backtrack(left-1, right)
        // undo the choice
        track = track[:len(track)-1]

        // make a choice, try to put a right parenthesis
        track += ")"
        backtrack(left, right-1)
        // undo the choice
        track = track[:len(track)-1]
    }

    backtrack(n, n)
    return res
}

var generateParenthesis = function(n) {
    let track = '';
    let res = [];

    const backtrack = (left, right) => {
        // if the remaining left parentheses are more, it is illegal
        if (right < left) return;
        // if the count is less than 0, it is definitely illegal
        if (left < 0 || right < 0) return;
        // when all parentheses are used up exactly, a legal combination of parentheses is obtained
        if (left === 0 && right === 0) {
            res.push(track);
            return;
        }

        // make a choice, try to put a left parenthesis
        track += '(';
        backtrack(left - 1, right);
        // cancel the choice
        track = track.slice(0, -1);

        // make a choice, try to put a right parenthesis
        track += ')';
        backtrack(left, right - 1);
        // cancel the choice
        track = track.slice(0, -1);
    }

    backtrack(n, n);
    return res;
};

With this, our algorithm is complete. What is the complexity of the algorithm? This is a bit tricky to analyze. For recursive algorithms, the time complexity is calculated as (number of recursive calls) * (time complexity of the recursive function itself).

backtrack is our recursive function, which contains no for loop code, so the time complexity of the recursive function itself is O(1). The key question is, how many times is this function called recursively? In other words, given an n, how many times is the backtrack function recursively invoked?

How did we analyze the number of recursive calls for dynamic programming algorithms before? It mainly depends on the number of "states," right? Actually, the essence of both backtracking and dynamic programming is exhaustive search, but dynamic programming can optimize "overlapping subproblems," while backtracking cannot.

So, we can also use the concept of "states" here. For the backtrack function, there are three states: left, right, track. The number of all possible combinations of these three variables is the number of states (call times) of the backtrack function.

The combination of left and right is straightforward; their values range from 0 to n, so there are only n^2 combinations. The length of track ranges from 0 to 2n, but for each length, there are exponentially many bracket combinations, which are hard to calculate.

After all this explanation, the point is to let you know that the complexity of this algorithm is exponential and not easy to calculate precisely. It is 4^n / sqrt(n). Interested readers can search for information about "Catalan numbers" to understand how this complexity is derived.