‘(‘ と’)’ のペアの組み合わせを全て列挙する問題です。
再帰を用いた例
以下は、再帰を用いた実装例です
class Solution {
public:
vector<string> generateParenthesis(int n) {
std::vector<std::string> return_value;
generateParenthesis(n, n, "", return_value);
return return_value;
}
private:
void generateParenthesis(int remaining_open, int remaining_close,
const std::string& temp, std::vector<std::string>& output) {
if (remaining_open == 0 && remaining_close == 0) {
output.push_back(temp);
return;
}
if (1 <= remaining_open) {
generateParenthesis(remaining_open - 1,
remaining_close,
temp + "(",
output);
}
if (remaining_open < remaining_close) {
generateParenthesis(remaining_open,
remaining_close - 1,
temp + ")",
output);
}
}
};N = 2 の場合、generateParenthesis(int, int, const std::string&, std::vector<std::string>&) の実引数は以下のようになります
少し複雑ですが、N = 3 になると以下のようになります
以上です！