回溯算法最佳實踐：括號生成

很多時候沒必要建全局變量，只要傳進去就好

比如說，輸入 n=3，輸出為如下 5 個字符串：
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

1、一個「合法」括號組合的左括號數(shù)量一定等于右括號數(shù)量，這個很好理解。
2、對于一個「合法」的括號字符串組合 p，必然對于任何 0 <= i < len§ 都有：子串 p[0…i] 中左括號的數(shù)量都大于或等于右括號的數(shù)量。

明白了合法括號的性質，如何把這道題和回溯算法扯上關系呢？
算法輸入一個整數(shù) n，讓你計算 n 對兒括號能組成幾種合法的括號組合，可以改寫成如下問題：
現(xiàn)在有 2n 個位置，每個位置可以放置字符 ( 或者 )，組成的所有括號組合中，有多少個是合法的？

#include <iostream> #include<bits/stdc++.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; #define maxn 10000 int res[10000]={0};///1:(,2:) int fin = 3; void backtrack(int left,int right) {if(left<right){return ;}///左一定比右多（我這里用的是已使用的個數(shù)） if(left>fin||right>fin){return ;}if(left==fin&&right==fin){for(int i=1;i<=fin*2;i++){if(res[i]==1){cout<<"(";}if(res[i]==2){cout<<")";}if(res[i]==0){break;}}cout<<endl;return ;}///res[left+right+1]=1;backtrack(left+1,right);res[left+right+1]=0;res[left+right+1]=2;backtrack(left,right+1);res[left+right+1]=0;} int main(int argc, char *argv[]) {ios::sync_with_stdio(0);cin.tie(0);backtrack(0,0);return 0; }

2021.3.9復習

很多思路，這里的left是已有的左括號數(shù)量，所以需要fin，left = =fin，但如果left為剩余可分配的左括號數(shù)量，left= =0為結束條件，就不用fin了

作者解題時是要實現(xiàn)函數(shù)，不能加全局變量，所以才用剩余

總結

以上是生活随笔為你收集整理的回溯算法-括号生成的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。