LeetCode 21. Generate Parentheses
811 ワード
remlostimeの問題解を参考にしました
戻り値retの参照を出力パラメータとして、カッコを再帰的に生成し、クリップを追加します:left_tot*2 > max_depの場合、すなわち現在押し込まれている左かっこの数(left_tot*2>2*n=max_dep=>left_tot>n)が総数nを超える場合に枝を切るとよい.
コード:
戻り値retの参照を出力パラメータとして、カッコを再帰的に生成し、クリップを追加します:left_tot*2 > max_depの場合、すなわち現在押し込まれている左かっこの数(left_tot*2>2*n=max_dep=>left_tot>n)が総数nを超える場合に枝を切るとよい.
コード:
class Solution
{
public:
vector<string> generateParenthesis(int n)
{
vector<string> ret;
gao(0, 2*n, 0, 0, string(), ret);
return ret;
}
private:
void gao(int dep, int max_dep, int left_now, int left_tot, string s, vector<string>& ret)
{
if (left_tot*2 > max_dep)
{
return ;
} else if (dep == max_dep)
{
ret.push_back(s);
return ;
}
gao(dep+1, max_dep, left_now+1, left_tot+1, s+'(', ret);
if (left_now > 0)
{
gao(dep+1, max_dep, left_now-1, left_tot, s+')', ret);
}
}
};