题目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题目大意

给定一个数,输出所有的能匹配的结果.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> res;  
    vector<string> generateParenthesis(int n) {
        string s;     
        DFS(s,n,n);
        return res;
    }
    void DFS(string s,int zuo,int you)
    {
        if(you<zuo) return;
        if(you==0 && zuo==0)
        {
            res.push_back(s);
            return;
        }
        if(zuo>0)   DFS(s+'(',zuo-1,you);  //!!!!!!!!!!!!!!!!!!!!!!!!!
        if(you>0)   DFS(s+')',zuo,you-1);  // !!!!!!!!!!!!!!!!!!!!!!!!
    }
};

解答

自己写的解法,首先看到求所有可能的值,想到用深度优先算法,

设置zuo ,you 两个指针,初始值为n,也就是有多少个,每次用一个就减一次.

和以往的DFS不同的地方在于DFS递归是有条件的递归,也就是个数是有限的,

感叹号的地方,不是每一次都要进行递归,而是满足条件才进行递归,

(和死胡同的区别,DFS中最开始两个if语句表示进入到这个胡同中,判断是不是符合的解,

这里感叹号的if表示的是没有这个胡同,但是程序不知道,你要告诉程序没有这个胡同)