LeetCode #22 – Generate Parentheses [DFS]

链接:https://leetcode.com/problems/generate-parentheses/

题目:

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

题意:给定括号的对数,返回所有可以一一配对的括号字符串序列

分析:DFS搜索即可,设定'(‘为1,’)’为-1,则所有符合条件的序列最终结果为0。当DFS递归的时候,不可能得到值<0或者>n的情况,应当剪枝或回溯。

CPP代码:

class Solution {
public:
    void DFS(string s, int cur, int n) {
        if(s.size() == 2 * n) {
            if(!cur) res.push_back(s);
            return;
        }
        if(cur > 0) DFS(s + ')', cur-1, n);
        if(cur < n) DFS(s + '(', cur+1, n);
    }
    vector<string> generateParenthesis(int n) {
        DFS("", 0, n);
        return res;
    }
private:
    vector<string> res;
};

欢迎留言