LeetCode—22.かっこ生成(Generate Parentheses)——分析とコード(C++)

LeetCode—22.括弧生成[Generate Parentheses]——分析及びコード[C+]

一、テーマ

二、分析及びコード

1. 遡及(DFS)

(1)考え方

(2)コード

(3)結果

三、その他

一、テーマ
nは括弧を生成する対数を表します.可能なすべての有効な括弧の組み合わせを生成できるように関数を書いてください.
たとえば、n=3が与えられ、結果は次のようになります.

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/generate-parentheses著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
二、分析及びコード
1.遡及(DFS)
(1)考え方
ターゲット対数に達するまで、可能なカッコを絶えず追加し、再帰的な方法で遡及します.カッコの有効な判断方法:1)左カッコ数が目標対数より小さい;2)右括弧数が左括弧数より小さい.
(2)コード

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<string> ans;
		backtrack(ans, "", 0, 0, n);
		return ans;
	}

	void backtrack(vector<string>& ans, string str, int l, int r, int n) {
		if (l + r == 2 * n) {
			ans.push_back(str);
			return;
		}
		if (l < n)
			backtrack(ans, str + "(", l + 1, r, n);
		if (r < l)
			backtrack(ans, str + ")", l, r + 1, n);
	}
};

(3)結果
実行時間:8 ms、すべてのC++コミットで84.90%のユーザーを破った.メモリ消費量:17.1 MBで、すべてのC++コミットで71.58%のユーザーを破った.
三、その他
注意結果ベクトルansを渡す場合は、関数パラメータを参照伝達に設定する必要があります.