先看一道题目:
括号生成。
输入一个整数
，罗列出所有有效的括号组合。有效的括号组合是指 左括号开始，右括号结束，并且每个左括号都可以在右侧找到对应的右括号闭合，每个右括号在左边也有对应的左括号闭合。
例如:
((())) 有效；
)))((( 无效，因为它以 ) 开始；
(())() 有效；
())()) 无效 右括号不能闭合；
())(() 无效， 中间的 )(方向不对。
输入 n = 1， 只有一种组合 "()"
输入 n = 3, 有 5 种组合 ["((()))","(()())","(())()","()(())","()()()"]
这道题是典型的回溯穷举搜索。我们很容易想到一种方法: 把所有可能的组合搜索出来，然后检查每个结果是不是满足有效性的条件。
有效性检查，可以用一个栈数据结构来测试，将字符串从左到右依次放进一个栈里，如果是左括号，就入栈，如果是新的元素是右括号，就从栈里弹出一个元素。以上步骤重复，直到字符串结束。
这时候，有效组合会导致栈里的元素刚好是 0， 当然，栈自始至终的操作必须没有异常，比如要弹出元素时，检查栈是否为空，如果空说明这个字符串组合某个地方出现了右括号更多的情况——有效组合实际上是指，从左到右任何一个下标 i ，从0到i ，左括号的数量比右括号多，并且当 i 增长到结尾时，左右括号数量相等。
检测有效性的程序
bool isValidParenthesisStr(const string &ans) {
std::stack<char> st;
for (char c: ans) {
if (c == '(') {
st.push(c);
} else if (c == ')') {
if (st.empty()) {
return false;
}
st.pop();
}
}
return st.empty();
}
利用回溯法穷举所有组合，然后检查结果是否合格的算法
void backtrack(int n, int i, std::string& ans, vector<string>& result;) {
if (i == n * 2) {
if (isValidParenthesis(ans)) {
result.push_back(ans);
}
return;
}
string optional_str = "()";
for (char c: optional_str) {
ans.push_back(c);
backtrack(n, i + 1, ans, result);
ans.pop_back();
}
}
vector<string> generateParenthesis(int n) {
string ans;
vector<string> result;
backtrack(n, 0, ans, result);
return result;
}
上一篇回溯法[]写过，回溯的效率关键在“剪枝” 环节，以上的解法我们没有做任何剪枝缩短穷举空间, 效率会大打折扣。
用一个简图说明这点:
下面这个图表示规模为 n = 2 的穷举空间树，最后我们在不符合的组合上打叉
剪枝空间示意图
上面的代码展示的算法，没有剪枝的过程，实际上是走完图中的所有路径，然后对每条路径产生的结果做一个检测。当 n 增加时，我们会发现路径树的规模是 。
使用剪枝的策略，我们会发现有些路径早早地就能被否掉，如图所示的右枝，第一个符号是 '')" ，无论怎么凑，这种情况都是不合法的，所以我们可以把该节点下面的整棵树”剪掉” 不用考虑。
在左侧的树中，我们沿着树节点往下走，如果发现到了某个节点，")" 的数量超过了 ”(" 的数量，说明经过该节点的所有路径都“坏掉了” ，剪掉它。
如果发现 “(" 的数量过多——超过了 ，那以这个节点的树也是坏的，需要剪掉。
通过这番操作，我们把遍历树的规模剪掉了一半还多。设想 n 增加到3，整棵树有 6 层，它的剪枝节点大同小异，只是 "(" 超过平衡点的地方会更深一些，随着树规模变大，剪枝的好处越发显现。
利用剪枝策略改写上面的算法：
关键是在每个节点，判断一下以该节点为根的子树是不是坏掉了。
void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
if (cur.size() == n * 2) {
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(ans, cur, open + 1, close, n);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
backtrack(ans, cur, open, close + 1, n);
cur.pop_back();
}
}
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
用 open 表示当前左括号的数量，close 表示当前右括号的数量。
如果 open 数量不到 n 就往 ans里填 "(" 如果 close 小于open 就往 ans 里填 ”)" ，注意上面代码的顺序，是一个深度优先搜索的顺序——尽可能先填满 ”(" ，填不下去之后就补 ")"
网友评论