Leetcode 22. Generate Parentheses (C++)

好像是經典題, 但第一時間我沒有任何想法

稍微google一下, DFS, 好樣的應該跟遞迴離不開關係了

我想到的是我們可以分成兩條路

1. 在左括號數量小於n 的情況下, 再加一個左括號
2. 加一個右括號後在遞迴

起初我的code長這樣

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n == 0) return vector<string>({});
        vector<string> res;
        int left = 0;
        int right = 0;
        string s;
        addParenthesis(n, left, right, res, s);
        return res;
    }
    void addParenthesis(int &n, int left, int right, vector<string> &res, string s){
        if(left < right) return;
        if(left < n){
            s = s + string("(");
            ++left;
            addParenthesis(n, left, right, res, s);
        }
        if(right < n ){
            s = s + string(")");
            ++right;
            addParenthesis(n, left, right, res, s);
        }
        
        if(left == n && right == n){
            res.emplace_back(s);
        }
        
    }
};

這樣做會發生一件事, 就是會有重複的答案, 除非讓vector變成set, 不然沒有邏輯的方式,

抱歉我一個邏輯欠缺, 首先我們改一下順序

if(left == n && right == n){
            res.emplace_back(s);
            return;
            }

判斷必須先放前面, 以免遞迴先做, 這是第一個點

另外 在每次遞迴之後, 必須pop out, 才不會有重複的, 這是第二個點, 最後完成會向下方

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n == 0) return vector<string>({});
        vector<string> res;
        int left = 0;
        int right = 0;
        string s;
        addParenthesis(n, left, right, res, s);
        return res;
    }
    void addParenthesis(int &n, int left, int right, vector<string> &res, string &s){
        if(left == n && right == n){
            res.emplace_back(s);
            return;
        }
        if(left < n){
            s = s + string("(");
            addParenthesis(n, ++left, right, res, s);
            s.pop_back();
            --left;
        }
        if(right < left){
            s = s + string(")");
            addParenthesis(n, left, ++right, res, s);
            s.pop_back();            
            --right;
        }
    }
};

謝謝收看, 放假放久真的會智商降低