回溯算法最佳实践：括号生成 :: labuladong的算法小抄 #1057
Replies: 28 comments 3 replies
-
|
这里的公式渲染有问题 |
Beta Was this translation helpful? Give feedback.
-
|
@michael728 感谢指出~ 已修复 |
Beta Was this translation helpful? Give feedback.
-
|
好文章，点赞 |
Beta Was this translation helpful? Give feedback.
-
|
Java版本： class Solution {
List<String> res;
public List<String> generateParenthesis(int n) {
res = new ArrayList<>();
backtrack(new StringBuilder(),n,n);
return res;
}
private void backtrack(StringBuilder sb,int cntl,int cntr){
if(cntr<cntl) return;
if(cntl<0||cntr<0) return;
if(cntl==0&&cntr==0){
res.add(sb.toString());
return;
}
sb.append('(');
backtrack(sb,cntl-1,cntr);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
backtrack(sb,cntl,cntr-1);
sb.deleteCharAt(sb.length()-1);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
关于回溯算法技巧的一个疑惑：如果满足结束条件，就把track加入result，有的时候需要在这里取消选择，有的时候又不需要？ |
Beta Was this translation helpful? Give feedback.
-
|
我觉得作者表述有误，叶子节点是没有选择的节点，没有选择何谈选择。即在回溯中，碰到没有选择的节点即可直接回归。 |
Beta Was this translation helpful? Give feedback.
-
|
@Warning-doid 看你怎么传递参数。所谓回溯，就是我们想要状态不变。如果用 pass-by-value 的形式来传参，数据本身是复制了，所以不用显式的撤回。如果是将共享的数据传，像例子里的 reference，就要显式的来回撤。 |
Beta Was this translation helpful? Give feedback.
-
|
对于 @Warning-doid 的问题，@z1ggy-o 你其实没说到点子上，准确来说，关键是看你结束递归的 base case。 如果 base case 在叶子节点上结束，因为叶子结点也是一个节点，所以 base case 里面也要进行「选择」和「撤销选择」。 如果 base case 在空节点上结束，那就不用考虑这些，直接 return 就好。 |
Beta Was this translation helpful? Give feedback.
-
|
请问这道题为什么不需要for来确定位置呢 |
Beta Was this translation helpful? Give feedback.
-
写了一个更轻快的版本，其中l和r分别代表还需要的左右括号数量 |
Beta Was this translation helpful? Give feedback.
-
|
想问一下，为什么先放了左括号再撤销，然后再放右括号，再撤销，这一块没太理解，哪位大佬能给解释一下？小白抱头. |
Beta Was this translation helpful? Give feedback.
-
|
你是没有看过回溯的框架吧？ |
Beta Was this translation helpful? Give feedback.
-
|
这是已经不是多叉树了是吧 |
Beta Was this translation helpful? Give feedback.
-
|
这个 怎么不按框架套路出牌，去掉了 for 我差点又进入脑补压栈了，还好跳出来了。 |
Beta Was this translation helpful? Give feedback.
-
|
@Rayso777 你好，我也是小白，但我这样理解的，希望能帮到你。实质这就是在穷举呀。回溯算法的思路就是：1.算法过程中穷举所有组合（满足题目条件的组合/不满足题目条件的组合）；2.从所有组合中排除不满足条件的组合，最后得到满足条件的组合。放到这道题具体而言：1.在此位置先放左括号，进行backTrack递归，就相当于以左括号为根节点生成一棵子多叉树，当走到if(left==0&&right==0)时就可以记录下“正确的组合”，否则在if(left>right)和if(left<0||right<0)就返回了。2.撤销左括号，意思就是这棵子多叉树已经走完了，下面准备再试试在此位置放置右括号会有哪些“正确的组合”。3.右括号同理。 |
Beta Was this translation helpful? Give feedback.
-
|
简单记录一下java版本 class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<>();
StringBuilder sb = new StringBuilder();
backTrack(n,n,result,sb);
return result;
}
private void backTrack(int leftCount,int rightCount,List<String> result,StringBuilder sb){
//如果左括号剩下的多 说明不符合要求
if(leftCount > rightCount) return;
//括号数量最后 变成了 负数 不合法
if(leftCount < 0 || rightCount < 0) return;
if(leftCount == 0 && rightCount == 0){
result.add(sb.toString());//找到一种可能 将结果加入到result集合中
}
sb.append('(');
backTrack(leftCount-1,rightCount,result,sb);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
backTrack(leftCount,rightCount-1,result,sb);
sb.deleteCharAt(sb.length()-1);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
nice |
Beta Was this translation helpful? Give feedback.
-
二刷补充说明，此处 为什么 |
Beta Was this translation helpful? Give feedback.
-
|
js版本 /**
* @param {number} n
* @return {string[]}
*/
/**
解题思路
1. 使用回溯算法，相当于生成一颗树
*/
var generateParenthesis = function(n) {
let res=[]
let track=[];
// left 括号数有n个， right 括号数也有n个
function backtrack(left,right,track){
if(left>right){ // 因为先消费的左边的，所以一定是左边的元素比右边的少
return ;
}
if(left<0||right<0){
return
}
if(left===0&&right===0){
res.push(track.slice().join(""));
return
}
track.push("(");
backtrack(left-1,right,track);// 消耗了一个左括号
track.pop();
track.push(")");
backtrack(left,right-1,track); // 消耗了一个右括号
track.pop();
}
backtrack(n,n,track);
return res
}; |
Beta Was this translation helpful? Give feedback.
-
|
记录一下，利用的是之前排列组合的思想解题，利用的是排列 元素可重不可重选，之前做的时候误用了组合的思路导致不对，其实后面想来用组合的话不就是2n选2n个，那就只有一种情况，显然不符合题意 class Solution {
List<String> res = new LinkedList<>();
StringBuffer track = new StringBuffer();
int trackSum = 0;
boolean[] used;
public List<String> generateParenthesis(int n) {
//把"("看作1
//把")"看作-1
//每次放进去需判断sum >= 0 不然不对，肯定是'('先于')'
//相当于组合加上个TrackSum
int[] nums = new int[2*n];
used = new boolean[2 * n];
//存放括号代表的int值，前n个是1(左括号)，后n个是-1(右括号)
for(int i = 0; i < n; i++){
nums[i] = 1;
nums[i + n] = -1;
}
backtrack(nums,trackSum);
return res;
}
//排列 元素可重不可重复选
void backtrack(int[] nums, int trackSum){
if(nums.length == track.length()){
res.add(new String(track));
trackSum = 0;
return;
}
for(int i = 0; i < nums.length; i++){
//剪枝
if(used[i]){
continue;
}
if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
if(trackSum + nums[i] < 0){
//保证trackSum一直 >=0，也就是左括号比右括号数量多
//小于0就不用append这一次
continue;
}
//做选择
if(nums[i] == 1){
track.append('(');
}else{
track.append(')');
}
used[i] = true;
trackSum += nums[i];
//递归
backtrack(nums, trackSum);
//撤销选择
used[i] = false;
track.deleteCharAt(track.length() - 1);
trackSum -= nums[i];
}
}
} |
Beta Was this translation helpful? Give feedback.
-
|
打卡，感谢！ |
Beta Was this translation helpful? Give feedback.
-
|
Java版，使用 class Solution {
public List<String> generateParenthesis(int n) {
// 可用的左括号和右括号数量初始化为 n
backtrack(n, n);
return res;
}
// 记录所有合法的括号组合
List<String> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Character> track = new LinkedList<>();
// 可用的左括号数量为 left 个，可用的右括号数量为 right 个
void backtrack(int left, int right) {
// 若左括号剩下的多，说明不合法
if (left > right) {
return;
}
// 数量小于 0 肯定是不合法的
if (left < 0 || right < 0) {
return;
}
// 当所有括号都恰好用完时，得到一个合法的括号组合
if (left == 0 && right == 0) {
res.add(applyAsString(track));
return;
}
// 尝试放一个左括号
// 做选择
track.addLast('(');
// 递归下一层回溯树
backtrack(left - 1, right);
// 撤销选择
track.removeLast();
// 尝试放一个右括号
// 做选择
track.addLast(')');
// 递归下一层回溯树
backtrack(left, right - 1);
// 撤销选择
track.removeLast();
}
String applyAsString(LinkedList<Character> track) {
StringBuilder sb = new StringBuilder(track.size());
for (Character ch : track) {
sb.append(ch);
}
return sb.toString();
}
} |
Beta Was this translation helpful? Give feedback.
-
|
贴一个C++双百版本，并且带for循环便于理解。实际上这里的for循环是可以省略的，因为同一个位置上只有两种情况: 左括号和右括号。前面带for循环是因为同一个位置的情况有k种，这里可以直接手写出来所以就省略for了 class Solution {
vector<string> res;
vector<char> dir {'(', ')'};
public:
void backtrack(int n, int left, int right, string& onPath) { // 放n个括号，代表左括号有n个，右括号也有n个，这样才合法。并且在每个位置i时，[0, i]中左括号的总数一定大于右括号的数量
if (left < 0 || right < 0) return;
if (right < left) return; // 如果右括号放的比左括号多，则不合法，返回
if (left == 0 && right == 0) {
res.push_back(onPath);
return;
}
for (auto a: dir) {
onPath.push_back(a);
if (a == '(') {
backtrack(n, left - 1, right, onPath);
} else {
backtrack(n, left, right - 1, onPath);
}
onPath.pop_back();
}
}
vector<string> generateParenthesis(int n) {
string onPath = "";
backtrack(n, n, n, onPath);
return res;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
我是这么想的：每一次插入一对括号，这样绝对能成功，但是可能重复，所以我用set去重。时间复杂度也很大，应该是O(n^n)。 class Solution {
public:
set <string> ans;
vector <string> a;
set <string> f[10] = {};
void dfs(string a, int n)
{
if (n == 0)
{
// ans.insert(a);
this -> a.push_back(a);
return;
}
if (a == "")
{
dfs("()", n - 1);
return;
}
for (int i = 0; i < a.size(); i ++)
{
string temp = a.substr(0, i + 1);
temp += "()";
temp += a.substr(i + 1, a.size());
if (f[n].count(temp))
{
continue;
}
f[n].insert(temp);
dfs(temp, n - 1);
}
}
vector<string> generateParenthesis(int n)
{
dfs("", n);
// vector <string> ans;
// for (auto i = this -> ans.begin(); i != this -> ans.end(); i ++)
// {
// ans.push_back(* i);
// }
// return ans;
return a;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
哦，刚刚的好像是另一个思路，就是用set[]让每一步都不会重复，空间复杂度大，这才是那个set去重的版本： class Solution {
public:
set <string> ans;
vector <string> a;
set <string> f[10] = {};
void dfs(string a, int n)
{
if (n == 0)
{
// ans.insert(a);
this -> a.push_back(a);
return;
}
if (a == "")
{
dfs("()", n - 1);
return;
}
for (int i = 0; i < a.size(); i ++)
{
string temp = a.substr(0, i + 1);
temp += "()";
temp += a.substr(i + 1, a.size());
if (f[n].count(temp))
{
continue;
}
f[n].insert(temp);
dfs(temp, n - 1);
}
}
vector<string> generateParenthesis(int n)
{
dfs("", n);
// vector <string> ans;
// for (auto i = this -> ans.begin(); i != this -> ans.end(); i ++)
// {
// ans.push_back(* i);
// }
// return ans;
return a;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
使用括号数量递增 class Solution {
List<String> result = new LinkedList<>();
public List<String> generateParenthesis(int n) {
dfs(0,0,n,new StringBuilder());
return result;
}
private void dfs(int left , int right , int n,StringBuilder sb){
if(right > left) return;
if(left > n || right > n) return;
if(left == n && right == n){
result.add(sb.toString());
return;
}
sb.append('(');
dfs(left+1,right,n,sb);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
dfs(left,right+1,n,sb);
sb.deleteCharAt(sb.length()-1);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
daka left， right 作为输入，表示左右还可用的括号数。 |
Beta Was this translation helpful? Give feedback.
-
|
可以在递归生成括号的过程中用一个 int 变量 val 记录左右括号的个数，左括号减1，右括号加1。当 val 小于 0 时说明此时 ')' 的个数大于 '(' 的个数，不合法；当 val 等于 0 时只能添加左括号（添加右括号也无妨，会在下一层递归判为不合法）；当 val 大于 0 时左右括号都可添加。最后通过 track 的长度与 val 的值来判断是否合法： class Solution {
public:
void backtrack(int val, string& track, vector<string>& res, int tracklen) {
if(val < 0) return;
if(track.length() == tracklen) {
if(val == 0)
res.push_back(track);
return;
}
track.push_back('(');
val++;
backtrack(val, track, res, tracklen);
val--;
track.pop_back();
track.push_back(')');
val--;
backtrack(val, track, res, tracklen);
val++;
track.pop_back();
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string track;
backtrack(0, track, res, 2 * n);
return res;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
写错了，是左括号加1，右括号减1。 |
Beta Was this translation helpful? Give feedback.
-
class Solution {
// 存放结果
List<String> results = new ArrayList<>();
// 存放一条路径上的值
List<Character> path = new ArrayList<>();
int left = 0; // 记录左括号的个数
int right = 0; // 记录右括号的个数
public void backTracking(int curDepth,int targetDepth){
if (curDepth == targetDepth){
if (left == right){
StringBuilder sb = new StringBuilder();
for (Character c: path)
sb.append(c);
results.add(new String(sb));
}
return;
}
// 放左括号
// 剪枝 满足条件才放入
if (left + 1 >= right){
left++;
path.add('(');
backTracking(curDepth + 1,targetDepth);
left--;
path.remove(path.size() - 1);
}
if (right + 1 <= left){
right++;
path.add(')');
backTracking(curDepth + 1,targetDepth);
right--;
path.remove(path.size() - 1);
}
}
public List<String> generateParenthesis(int n) {
backTracking(0,2 * n);
return results;
}
} |
Beta Was this translation helpful? Give feedback.
-
剪个枝，go版本func generateParenthesis(n int) []string {
res := make([]string, 0)
track := make([]byte, 0)
// i,j分别表示'('和')'已经放置的数量
var backtrack func(i, j int)
backtrack = func(i, j int) {
if i == n && j == n {
res = append(res, string(track))
return
}
// 选择'('
if i != n {
track = append(track, '(')
backtrack(i+1, j)
track = track[:len(track)-1]
}
// 前面'('的数量必须大于')'的数量才能选择')'
if i > j {
track = append(track, ')')
backtrack(i, j+1)
track = track[:len(track)-1]
}
}
backtrack(0, 0)
return res
} |
Beta Was this translation helpful? Give feedback.
and others
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里：回溯算法最佳实践：括号生成
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions