數字 n 代表生成括號的對數，請你設計一個函式，用于能夠生成所有可能的并且 有效的 括號組合，
看到該題目我首先的想法是采用遞推的方式去實作該題目，但是發現會生成重復的元素，因此我采用了dfs剪去不合適的分支的方法來處理該題目，需要剪枝的情況有三種，左括號數目大于n，右括號數目大于n，左括號數目小于右括號數目，這里我們重點說一下第三種情況，因為在括號序列中，一定是先生成左括號再生成右括號，因此一定是左括號的數目大于等于右括號的數目，否則就會出錯，程式代碼如下：
#include <cstdio> #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; vector<string> generateParenthesis(int n); void func(vector<string>& res, string str, int l, int r, int n); int main() { int n; cin >> n; vector<string> ans = generateParenthesis(n); for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << endl; } return 0; } vector<string> generateParenthesis(int n) { vector<string> res; func(res, "", 0, 0, n); return res; } void func(vector<string>& res, string str, int l, int r, int n) { if (l > n || r > n || r > l) return; if (l == n && r == n) { res.push_back(str); return; } func(res, str + '(', l + 1, r, n); func(res, str + ')', l, r + 1, n); return; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40786.html
標籤：C++
上一篇：WDK驅動除錯問題點滴
下一篇：C++中strcpy_s（）