dsa-competitive-programming/leetcode/lc22/optimalGenerateParantheses.cpp

class Solution {
public:
    vector<string> ans;
    void helper(string s,int open,int close) {
        if(open==0 && close==0) {
            ans.push_back(s);
            return;
        }
        if(open>0) {
            s+='(';
            helper(s,open-1,close);
            s.pop_back();
        }
        if(close>0) {
            if(open<close) {
                s+=')';
                helper(s,open,close-1);
                s.pop_back();
            }
        }
        return;
    }
    vector<string> generateParenthesis(int n) {
        helper("",n,n);
        return ans;
    }
};

//This solution uses DFS with backtracking to generate all valid parentheses by exploring one complete construction path at a time.
//pop_back() is used to backtrack by removing the last added character, as string s is passed by reference, hence more optimal

//TC : O(Cn), catalan number, The number of valid parentheses strings with n pairs is the n-th Catalan number.
//SC: O(n)