//
//  Solution22.hpp
//  Algorithm
//
//  Created by Pancf on 2019/12/9.
//  Copyright © 2019 Pancf. All rights reserved.
//

#ifndef Solution22_hpp
#define Solution22_hpp

#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::string;

class Solution22 {
/**
 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:

 [
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
 ]
 ================================================================================================
 Accept details:
 Runtime: 4 ms, faster than 88.73% of C++ online submissions for Generate Parentheses.
 Memory Usage: 13.8 MB, less than 87.60% of C++ online submissions for Generate Parentheses.
 思路：这是一道非常典型的backtracking题，backtracking可以想象为从树的根节点出发，每个节点的下一步会有几种可能性就有几个分支，比如这道题里
 现有的字符串下一步可以插入'('或')'，那么每个节点就有两个分支，选择其中一个分支往下走一步，判断是否还是符合限制，如果符合则往下走，如果不符合
 则回退，并且把这个分支剪枝。backtracking类型的题目可以归结为以下思路
 procedure bt(c)
    if reject(P,c) then return       #不满足限制条件则剪枝，然后return
    if accept(P,c) then output(P,c)  #满足全部条件，根据需要输出或者保存结果，然后return
    s ← first(P,c)                   #获取当前节点的第一个分支，比如这道题里的push '('
    while s ≠ NULL do                #判断往下走了一步以后是否满足条件，满足的话递归调用，不满足的话则会return。选择分支是用if-else还是循环视情况而定
        bt(s)
        s ← next(P,s)                #获取下一个分支
*/
public:
    vector<string> generateParenthesis(int n);
    static void test() {
        Solution22 s = Solution22();
        auto rv = s.generateParenthesis(3);
        for (auto str : rv) {
            std::cout<<str<<std::endl;
        }
    }
};
#endif /* Solution22_hpp */