前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Think

題目給了一個n(介於1-8)，每個n代表一組()，要找出這些()*n個可以組出的合理組合，也就是每一個(一定要有)去對應

• 一開一關~

寫到有點卡住，看了一下Neetcode上的影片圖解部分，主要有兩個判斷條件：

1. "("的數量 < n，表示目前還可以繼續放(，Code中open_p代表的是"("的數量。
2. ")"的數量 < "("的數量，表示目前有(存在，所以可以放)配成一對Code中close_p代表的是")"的數量。。
3. 最後是停止條件的部分，如果找出的組合數量等於n * 2的話，就結束了~

Code

#include <vector>
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    void backtrack(vector<string> &output, string current_str, int open, int close, int n){
        if (current_str.length() == n*2){
            // cout << current_str << endl;
            output.push_back(current_str);
            return;
        } 
        if (open < n){
            backtrack(output, current_str + '(', open + 1, close, n);
        }
        if (close < open){
            backtrack(output, current_str + ')', open, close + 1, n);
        }
    }
};

Submission

今天就到這邊啦~
大家明天見