Does anyone come up with a non-recursion solution?


  • 11
    W

    I used recursion as below:

    class Solution:
    
        def generateParenthesis(self, n):
            if (n == 0):
                return []
            string = "("
            result = []
            left_number = 1
            right_number = 0
            self.solve(left_number, right_number, string, n, result)
            return result
            
        def solve(self, l_n, r_n, string, n, result):
            if (l_n == r_n and r_n == n):
                result.append(string)
                return
            
            if (l_n < n):
                self.solve(l_n+1, r_n, string+'(', n, result)
                
            if (r_n < l_n):
                self.solve(l_n, r_n+1, string+')', n, result)
    

    I am trying to get an iteration solution but haven't got a clue yet.


  • 0
    J

    I've got one here. Starting with "(", add '(' or ')' to the end of string

    struct _sto {
        int left;
        int right;
        string s;
    };
    
    class Solution {
        vector<string> pairs;
    public:
        vector<string> generateParenthesis(int n) {
            struct _sto a;
            struct _sto b;
            if (n <= 0)  return pairs;
            a.left = n-1;
            a.right = n;
            a.s = "(";
            queue<struct _sto> q;
            q.push(a);
            a.left = -1;      // mark the end of current round
            q.push(a);
            int end = 2*n-1;
            for (int i = 0; i < end; i++) {
                while(1) {
                    a = q.front();
                    q.pop();
                    if (a.left == -1) {
                        q.push(a);
                        break;
                    }
                    b.left = a.left;
                    b.right = a.right;
                    b.s = a.s;
                    if (a.right == 0)  continue;
                    if (a.left >0) {
                        a.s.push_back('(');
                        a.left--;
                        q.push(a);
                    }
                    if (b.right > b.left) {
                        b.s.push_back(')');
                        b.right--;
                        q.push(b);
                    }
                }
            }
            while (q.size() != 0) {
                a = q.front();
                q.pop();
                if (a.left == -1)  continue;
                pairs.push_back(a.s);
            }
            return pairs;
        }
    
    };

  • 0
    X

    Record the result with smaller n. Then we can use the previous result to generate new result.

    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        if (!n) {
            return ret;
        }
        
        vector<vector<string> > cache(n+1);
        cache[1] = vector<string>(1, "()");
        
        for (int i=2;i<=n;i++) {
            vector<string> vt;
            for (int j=0;j<=(i-1)/2;j++) {
                vector<string>& left = cache[j];
                vector<string>& right = cache[i-1-j];
                if (j == 0) {
                    for (int l=0;l<right.size();l++) {
                        vt.push_back(string("()") + right[l]);
                        vt.push_back(string("(") + right[l] + string(")"));
                    }
                } else {
                    for (int k=0;k<left.size();k++) {
                        for (int l=0;l<right.size();l++) {
                            vt.push_back(string("(") + left[k] + string(")") + right[l]);
                            if (i-1-j != j) {
                                vt.push_back(string("(") + right[l] + string(")") + left[k]);
                            }
                        }
                    }
                }
            }
            
            cache[i] = vt;
        }
        
        return cache[n];
    }

  • 34
    3

    Start from "(", keep appending "(" and / or ")" with a string stack, till we reach the length 2 * n then output all combinations. The problem here is... we may generate invalid strings if we do this freely, to avoid that, we should keep an additional stack of integer to store the value of v which is the number of closed parenthesis in the current string -- if v * 2 >= current string length, means we would be adding too many ')'; if current string length - v >= n, means we would be adding too many '('. otherwise we could append both and push them into the string stack.

    public List<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<String>();
        Stack<String> stack = new Stack<String>();
        Stack<Integer> validationStack = new Stack<Integer>();
        stack.push("(");
        validationStack.push(0);
        while(stack.size() != 0)
        {
            String s = stack.pop();
            int v = validationStack.pop();
            if(s.length() == n * 2)
            {
                list.add(s);
                continue;
            }
            if(s.length() - v < n)
            {
                stack.push(s + "(");
                validationStack.push(v);
            }
            if(2 * v < s.length())
            {
                stack.push(s + ")");
                validationStack.push(v+1);
            }
        }
        return list;
    }

  • 3
    R

    I have one solution in Java. It is pretty straightforward.

    public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result=new LinkedList<String>();
        
        if (n==0) return result;
        
        Deque<Integer> left_queue = new LinkedList<Integer>();
        Deque<Integer> right_queue = new LinkedList<Integer>();
        Deque<String> string_queue = new LinkedList<String>();
        
        left_queue.addFirst(n-1);
        right_queue.addFirst(n);
        string_queue.addFirst("(");
        
        while (!string_queue.isEmpty()){
            int left = left_queue.pollLast();
            int right = right_queue.pollLast();
            String string=string_queue.pollLast();
            
            if (left>0){
                string_queue.addLast(string+"(");
                left_queue.addLast(left-1);
                right_queue.addLast(right);
            }
            if (right>0&&right>left){
                string_queue.addLast(string+")");
                left_queue.addLast(left);
                right_queue.addLast(right-1);
            }
            
            if (right==0&&left==0)
                result.add(string);
        }
        
        return result;
    }
    

    }


  • 0
    R

    Well my answer is exactly straightforward as yours. The key is to use queues to store your results.


  • 0
    R

    Nice algorithm.


  • 0
    T

    Here is my accepted solution, the basic idea is adding parentheses pairs one by one.

    public List<String> generateParenthesis(int n) {
        ArrayList<String> rs=new ArrayList<String>();
        rs.add("");
        
        String pre_result="";
        for(int i=0; i<n; i++){
            int origin_size=rs.size();
            for(int j=0; j<origin_size; j++){
                pre_result=rs.get(0);
                rs.remove(0);
                
                int last_pos=pre_result.lastIndexOf('(');
                for(int k=last_pos+1; k<=pre_result.length(); k++){
                    rs.add(pre_result.substring(0, k)+"("+pre_result.substring(k)+")");
                }
            }
        }
        
        return rs;
    }
    

  • 11
    F

    Here is my accepted Java solution:

    public List<String> generateParenthesis(int n) {
    	List<String> result = new LinkedList<>();
    	result.add("()");
    	for (int i = 1; i < n; ++i) {
    		Set<String> buffer = new HashSet<>();
    		for (int j = 0; j < result.size(); ++j) {
    			String str = result.get(j);
    			for (int k = 0; k < str.length(); ++k) {
    					buffer.add(str.substring(0, k) + "()" + str.substring(k, str.length()));
    			}
    		}
    		result.clear();
    		result.addAll(buffer);
    	}
        return result;
    
    • n=1, it is "()"
    • n=2, we need to add a new () into all locations of "()": ()(), (()) and ()(). Just remember to remove duplicates. So the final result is: ()() and (())
    • n=3, we will add a new () into all locations of ()() and (()) ...
    • ...
    • n=n...

  • 17
    J

    DP based solution:

    public static List<String> generateParenthesis(int n) {
    	List<String>[]  result = new List[n+1];
    	result[0] = Arrays.asList("");
    	for(int i=1; i<=n; i++){
    		List<String> r = new ArrayList<String>();
    		for(int j=0; j<i; j++){
    			for(String sl : result[j])
    				for(String sr : result[i-j-1])
    					r.add("(" + sl + ")" + sr);
    		}
    		result[i] = r;
    	}
    	return result[n];
    }

  • 0
    Z

    Here is what I have, a bottom-up solution.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> ret;
            if (n == 0) {
                return ret;
            }
            
            unordered_set<string> retSet;
            for (int i = 1; i <= n; i ++) {
                if (i == 1) {
                    retSet.insert("()");
                } else {
                    unordered_set<string>::iterator it;
                    unordered_set<string> tmpSet;
                    for (it = retSet.begin(); it != retSet.end(); it ++) {
                        for (int j = 0; j < (*it).size() + 1; j ++) {
                            string oneVal = "";
                            if (j == 0) {
                                oneVal = "()" + (*it);
                            } else if (j == (*it).size()) {
                                oneVal = (*it) + "()";
                            } else {
                                oneVal = (*it).substr(0, j) + "()" + (*it).substr(j);
                            }
                            if (tmpSet.find(oneVal) == tmpSet.end()) {
                                tmpSet.insert(oneVal);
                            }
                        }
                    }
                    retSet = tmpSet;
                }
            }
            unordered_set<string>::iterator it;
            for (it = retSet.begin(); it != retSet.end(); it ++) {
                ret.push_back(*it);
            }
            return ret;
        }
    };

  • 0
    F

    cool algorithm.


  • 0
    H

    how do you know all the combination is covered?


  • 0
    I

    "if v * 2 >= current string length, means we would be adding too many ')'; if current string length - v >= n, means we would be adding too many '(' " I can't get the idea of this line. Could you explain it?


  • 0
    M

    What is the time complexity?


  • 0
    3

    It is actually traveling a binary tree which contains all available combinations at leaf nodes. Only the invalid branches are skipped.


  • 0
    3

    Should be two times of the count of all available combinations


  • 0
    3

    v is the count of ")" , while s.length() -v is the count of "(". Say n = 2, either "((()" or "()))" are invalid since s.length()-v=3>n (some "(" won't be closed up) and s.length() -v =1< v (some ")" have no counter part). Hope this make sense...


  • 0
    H

    I got one using DP method with C++.

    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if(n<1)
            return result;
        vector<vector<string> > buff(n+1,vector<string>());
        buff[0]=vector<string>(1,"");
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                for(int k=0;k<buff[j].size();k++)
                    for(int l=0;l<buff[i-j-1].size();l++)
                        buff[i].push_back(buff[j][k]+"("+buff[i-j-1][l]+")");
            }
        }
        return buff[n];
    }

  • 0
    S

    Your idea is awesome


Log in to reply
 

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