括号生成，力扣上原题，有一些疑惑
课程设计
1
问：来一个认真负责的大佬，详细列举举例一下回溯的过程，我一直不停的推导void backtrack，例如n=3，我只得到了（（（）））一个结果，希望详细一点 力扣上的原题的官方解析，回溯法，来一个认真负责的大佬
class Solution {
void backtrack(vector& 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();
}
}
public:
vector generateParenthesis(int n) {
vector result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
};
-
#include <vector> #include <string> #include <iostream> using namespace std; class Solution { 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('('); cout << cur << endl; backtrack(ans, cur, open + 1, close, n); cur.pop_back(); cout << cur << endl; } if (close < open) { cur.push_back(')'); cout << cur << endl; backtrack(ans, cur, open, close + 1, n); cur.pop_back(); cout << cur << endl; } } public: vector<string> generateParenthesis(int n) { vector<string> result; string current; backtrack(result, current, 0, 0, n); return result; } }; int main(void) { Solution su; vector<string> r = su.generateParenthesis(2); cout << "result is: " << endl; for (int i = 0; i < r.size(); ++i) { cout << r[i] << endl; } return 0; } -
public class Solution { List<string> list=new List<string>(); public IList<string> GenerateParenthesis(int n) { AAA("",n,0); return list; } public void AAA(string str, int left,int right) { if(left==0&&right==0) list.Add(str); if(left>0) { string Lstr= str+"("; AAA(Lstr,left-1,right+1); } if(right>0) { string Rstr= str+")"; AAA(Rstr,left,right-1); } } }
发表回复