What's wrong with my non-recursive solution?


  • 0
    C

    I feel that all possible combinations have been generated, only the order is different from the OJ's solution.
    The idea is simple. Start from "()". There are two ways to add parentheses:

    1. Add a pair of parentheses on the outside, so it becomes "(())".
    2. Add a pair of parentheses on the left or/and (depending on whether they are the same) on the right, so it becomes "()()".

    And we iterate the whole process.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> od={"()"};
            vector<string> nw;
            for(int i=1;i<n;i++){
                for(int j=0;j<od.size();j++){
                    nw.push_back("(" + od[j] + ")");
                }
                for(int j=0;j<od.size();j++){
                    string x1 = od[j] + "()";
                    string x2 = "()" + od[j];
                    if( x1.compare(x2)!=0 ) nw.push_back(x1);
                    nw.push_back(x2);
                }
                od = nw;
                nw.clear();
            }
            return od;
        }
    };
    

  • 0
    B

    I tried the same thing and realized the assumption isn't correct.

    For example, when n == 4 then one of the values is "(())(())" which cannot be constructed using that algorithm.


  • 0
    C

    Not the best solution but ACed.
    n pair solution is either "(" + n-1 pair solution + ")"
    or k pair solution + n-k pair solution for k=1..n-1
    To ensure uniqueness, we use set to avoid repetitive insertions.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<vector<string>> od={{"()"}};
            for(int i=1;i<n;i++){
                set<string> nw;
                for(int k=0;k<od[i-1].size();k++) nw.insert("(" + od[i-1][k] + ")");
                for(int k=0;k<i;k++){
                    for(int p=0;p<od[k].size();p++){
                        for(int q=0;q<od[i-k-1].size();q++){
                            nw.insert(od[k][p]+od[i-k-1][q]);
                        }
                    }
                }
                vector<string> tp(nw.begin(),nw.end());
                od.push_back(tp);
            }
            return od.back();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.