【Leet Code】22. Generate Parentheses

韩旭051

发布于 2019-11-08 00:41:50

3070

发布于 2019-11-08 00:41:50

文章被收录于专栏：刷题笔记刷题笔记

本文链接：https://blog.csdn.net/shiliang97/article/details/102000037

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:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs("",n,0);
        return result;
    }
private:
    vector<string> result;
    void dfs(string s,int left,int right)
    {
        if(left==0 && right ==0){
            result.push_back(s);
            return;
        }
        if(left>0) dfs(s+"(",left-1,right+1);
        if(right>0) dfs(s+")",left,right-1);
    }
};

传字符串，变成传字符串指针，节约了一半时间

class Solution {
public:
		vector<string> generateParenthesis(int n) {
			vector<string> result;
			string temp = "";
			dfsGP(result, temp, n, n, n);
			return result;
		}
		void dfsGP(vector<string>& result, string& cur, int n, int lN, int rN) {
			if (!lN) {
				for (int i = 0; i < rN; ++i)
					cur.push_back(')');
				result.push_back(cur);
				for (int i = 0; i < rN; ++i)
                    cur.pop_back();
			}
			else {
                cur.push_back('(');
				dfsGP(result, cur, n, lN - 1, rN);
                cur.pop_back();
				if (rN > lN) {
                    cur.push_back(')');
					dfsGP(result, cur, n, lN, rN - 1);
                    cur.pop_back();
				}
			}
		}
};