-
Notifications
You must be signed in to change notification settings - Fork 48
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
回溯算法 #24
Labels
Comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
概念
具有限界条件的 DFS (Depth first search,深度优先搜索)算法称为回溯算法。
例子
LeetCode 的第 22 题
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题目目的是给你一个数 n 写出来所有中可能的括号集合。
对于这道题,有以下的限制条件:
1、如果左括号已经用完了,则不能再加左括号
2、如果已经出现的右括号和左括号一样多,则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。
结束条件是:
左右括号都已经用完。
因此,把上面的思路写一下伪代码:
具体实现:
The text was updated successfully, but these errors were encountered: