思路：回溯

  • 树的左指针表示(，树的右指针表示),分别用left和right计数，如果left < num，那么允许走左边；如果left > right，那么允许走右边。每个节点一共两个分支。
  • ss.pop_back()体现了回溯的思想，否则不会往上走。
  • image.png

代码：

  1. class Solution {
  2. public:
  3.     void dfs(int n, int cur_index, vector<string>& res, string& ss, int left, int right) {
  4.         if (cur_index == 2 * n) {
  5.             res.push_back(ss);
  6.             return;
  7.         }
  9.         if (left < n) {
  10.             ss.push_back('(');
  11.             dfs(n, cur_index + 1, res, ss, left + 1, right);
  12.             ss.pop_back();
  13.         }
  15.         if (right < left) {
  16.             ss.push_back(')');
  17.             dfs(n, cur_index + 1, res, ss, left, right + 1);
  18.             ss.pop_back();
  19.         }
  22.     }
  23.     vector<string> generateParenthesis(int n) {
  24.         vector<string> res;
  25.         string ss;
  26.         dfs(n, 0, res, ss, 0, 0);
  27.         return res;
  28.     }
  29. };