LeetCode 22 – Generate Parentheses


Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

X. DP
https://discuss.leetcode.com/topic/3474/an-iterative-method
First consider how to get the result f(n) from previous result f(0)...f(n-1).
Actually, the result f(n) will be put an extra () pair to f(n-1). Let the "(" always at the first position, to produce a valid result, we can only put ")" in a way that there will be i pairs () inside the extra () and n - 1 - i pairs () outside the extra pair.
Let us consider an example to get clear view:
f(0): ""
f(1): "("f(0)")"
f(2): "("f(0)")"f(1), "("f(1)")"
f(3): "("f(0)")"f(2), "("f(1)")"f(1), "("f(2)")"
So f(n) = "("f(0)")"f(n-1) , "("f(1)")"f(n-2) "("f(2)")"f(n-3) ... "("f(i)")"f(n-1-i) ... "(f(n-1)")"
The equation is equivalent to the following one:
f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)
First, let f(n) to be a correct solution set when there is n pair of parentheses.
This means every combination in f(n) is a valid combination, and any combination which isn't in f(n) is not a valid combination for n.
And we can easily get the first three solution sets i.e. f(0) = {""}, f(1) = {"()"} f(2) = {"()()", "(())"}.
For any n > 2, each combination of f(n) can be divided into two parts p0 and p1.
p0 and p1 has several properties:
  1. Parentheses in both p0 and p1 can match wel
  2. p0 should be as short as possible but not empty. This means that p0 belongs to (f(l0-1)) where l0 is the number of pairs in p0.
    This property can be proved easily. Shortest means the first left parenthesis in this combination always matches the last right parenthesis.
    So without these two, what left is also a legal combination.
Now, let's reorganize f(n) by p0.
Put those combinations with same length of p0 into a same set, and then f(n) is divided into several subsets.
Each combination in subset s whose p0 has l0 pair of parentheses also belongs to the set (f(l0-1))f(n-l0).
So we can get f(n) belongs to (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0).
OK, the only thing to prove now is (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0) also belongs to f(n).
Notice that each combination in (f(i))f(n-1-i) is a legal combination for n, and we've declared before that each legal combination for n belongs to f(n).
So each combination in the left side of equation belongs to f(n), and the left side as a whole set belongs to f(n).
    public List<String> generateParenthesis(int n)
    {
        List<List<String>> lists = new ArrayList<>();
        lists.add(Collections.singletonList(""));
        
        for (int i = 1; i <= n; ++i)
        {
            final List<String> list = new ArrayList<>();
            
            for (int j = 0; j < i; ++j)
            {
                for (final String first : lists.get(j))
                {
                    for (final String second : lists.get(i - 1 - j))
                    {
                        list.add("(" + first + ")" + second);
                    }
                }
            }
            
            lists.add(list);
        }
        
        return lists.get(lists.size() - 1);
    }
https://discuss.leetcode.com/topic/20880/my-java-code-using-dp
The idea is clear. Use cache to store the already calculated results, from f(0) to f(n). For each f(i), get f(j) and f(i - j - 1) from cache, 0 <= j < = j-1.
public static List<String> generateParenthesis(int n) {
    List<List<String>> cache = new LinkedList<>(); // use arraylist or map
    cache.add(Arrays.asList(""));

    for (int i = 1; i <= n; i++) {
        List<String> nList = new LinkedList<>();
        for (int j = 0; j < i; j++) {
            List<String> inside = cache.get(j);
            List<String> tail = cache.get(i - j - 1);
            for (int k = 0; k < inside.size(); k++) {
                for (int l = 0; l < tail.size(); l++) {
                    nList.add("(" + inside.get(k) + ")" + tail.get(l));
                }
            }
        }
        cache.add(nList);
    }
    return cache.get(n);
}

X. BFS - Using Queue
https://richdalgo.wordpress.com/2014/12/21/generate-parentheses-bfs-dfs/
http://blog.sina.com.cn/s/blog_b9285de20101oa9t.html
class Elem {
    int left;
    int right;
    String str;
    Elem(int l, int r, String s) {
        left = l;
        right = r;
        str = s;
    }
}
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<String>();
    Queue<Elem> queue = new LinkedList<Elem>();
    queue.add(new Elem(0,0,""));
    while (!queue.isEmpty()) {
        Elem elem = queue.poll();
        if (elem.left == elem.right && elem.left == n) {
            result.add(elem.str);
        }
        if (elem.left >= elem.right && elem.left < n) {
            queue.add(new Elem(elem.left+1, elem.right, elem.str + "("));
        }
        if (elem.left >= elem.right && elem.right < n) {
            queue.add(new Elem(elem.left, elem.right+1, elem.str + ")"));
        }
    }
    return result;
}
find the last occurrence position P of '(' in the previous result, and append '(' + the rest + ')' to it from P+1 to end;
  1.     vector<string> generateParenthesis(int n)   
  2.     {  
  3.         vector<string> res;  
  4.         res.push_back("");  
  5.         for(int i=0;i<n;i++)  
  6.         {  
  7.             vector<string> tmp;  
  8.             for(int j=0;j<res.size();j++)  
  9.             {  
  10.                 int pos = res[j].rfind('(');  
  11.                 for(int k=pos+1;k<=res[j].size();k++)  
  12.                 {  
  13.                     tmp.push_back(res[j].substr(0,k) +  
  14.                         '(' + res[j].substr(k) + ')');  
  15.                 }  
  16.             }  
  17.             res = tmp;  
  18.         }  
  19.         return res;  
  20.     }  
public List<String> generateParenthesis(int n) {
 ArrayList<String> result = new ArrayList<String>();
 ArrayList<Integer> diff = new ArrayList<Integer>();
 
 result.add("");
 diff.add(0);
 
 for (int i = 0; i < 2 * n; i++) {
  ArrayList<String> temp1 = new ArrayList<String>();
  ArrayList<Integer> temp2 = new ArrayList<Integer>();
 
  for (int j = 0; j < result.size(); j++) {
   String s = result.get(j);
   int k = diff.get(j);
 
   if (i < 2 * n - 1) {
    temp1.add(s + "(");
    temp2.add(k + 1);
   }
 
   if (k > 0 && i < 2 * n - 1 || k == 1 && i == 2 * n - 1) {
    temp1.add(s + ")");
    temp2.add(k - 1);
   }
  }
 
  result = new ArrayList<String>(temp1);
  diff = new ArrayList<Integer>(temp2);
 }
 
 return result;
}

For n=2, we can construct the result set by inserting a new pair “()” into all gaps in the each of the result from n=1. For example, for n=1 result = {()} that has only one solution () that has total 3 gaps as follows –
      (  )
     ^  ^  ^
    g1  g2  g3
So, In order to get result for n=2 we will append () in each gap of each of the solutions of n=1 as follows –
     ()()         (())       ()()
     ^             ^           ^
    g1             g2          g3
The final result set (unique elements) for n=2 would be {()(), (())}.
So, in general there are m+1 gaps in a parenthesis of length m. So, we can construct the string with n parenthesis by inserting “()” into each of the m+1 gaps of the each of the solution of length m in result set for n-1.
How to implement this? We can formulate this problem as a Tree traversal problem where starting from n=1 as root “()” we traverse m+1=2+1=3 children corresponding to the string constructed by inserting “()” into each of the m+1 gaps. So, nodes at a level n of this tree will contain all possible strings with n pair of parenthesis. For
 
                        ( )           <- n = 1
                   /     |    \ 
            ( ) ( )   (())   ()()     <- n = 2
           / |  \ \ \      
     ()()() (())()     .........      <- n = 3
So, we can do a level order traversal using a queue and stop at level = n at which point the queue will contains the result set for n. 
public static ArrayList<String> genParanthesis(int n){
 ArrayList<String> res = new ArrayList<String>();
 if(n <= 0){
  return res;
 }
 if(n == 1){
  res.add("()");
  return res;
 }
 
 Queue<StringBuilder> queue = new ArrayDeque<StringBuilder>();
 Set<String> visited = new HashSet<String>();
 queue.add(new StringBuilder("()"));
 int count = 1;
 int level = 1;
 
 //do a level order (BFS) trversal upto level=n
 while(!queue.isEmpty()){
  StringBuilder node = queue.poll();
  String cur = node.toString();
  count--;
  visited.add(cur);
  
  //at the end of level order traversal upto level n the queue will contain all the leaves at level n
  //which are basically all possible strings constructed with n pair of parenthesis
  if(level == n){
   res.add(cur);
   continue;
  }
  
  //if not reached level n yet, then do BFS level order
  //there are total 1+len(cur) gaps
  for(int gap = 0; gap < cur.length()+1; gap++){
   //we create a child by putting () to each of the gap positions
   StringBuilder child = new StringBuilder(cur).insert(gap, "()");
   if(!visited.contains(child.toString())){
    queue.add(child);
    visited.add(child.toString());
   }
  }
  
  //end of a level
  if(count == 0){
   level++;
   count = queue.size();
  }
 }
 
 return res;
}
Alternative Recursive Approach
The idea is to keep two counters, one for number of remaining left parenthesis and the other for total number of remaining right parenthesis to be added. Each time we add a right parenthesis if remaining is greater than 0. We also balance it by adding left parenthesis only if remaining right is greater than 0. Below is the implementation of this algorithm.
public List<String> generateParenthesis(int n) {
    ArrayList<String> res = new ArrayList<String>();
 if(n <= 0){
     return res;
 }
 generate("", n, 0, res);
 return res;
}

public void generate(String str, int left, int right, ArrayList<String> res){
    if(right == 0 && left == 0){
        res.add(str);
    } 
    if(right > 0){
        generate(str+")", left, right-1, res);
    }
    if(left > 0){
        generate(str+"(", left-1, right+1, res); // left-1???
    }
}

===>like bfs, but not good implementation
  public ArrayList<String> generateParenthesis(int n) {
          
         ArrayList<Set<String>> list = new ArrayList<Set<String>>();
          
         int number=1;
          
         while (number<=n){
             Set<String> parentheses = new HashSet<string>();
             //generate combinations of pattern "("+[number-1]+")"
             generateParentheses(number,list,parentheses);
             //generate combinations of pattern [1][number-1],[2][number-2],...[number-1][1]
             for(int i=1;i<number;i++){
                 int leftIndex=i-1;
                 int rightIndex=number-i-1;
                 for(String left:list.get(leftIndex)){
                     for(String right:list.get(rightIndex)){
                         parentheses.add(left+right);
                     }
                 }
             }
             //add results of this number and go on.
             list.add(parentheses);
             number++;
         }
         //add the elements to list required by OJ.
         ArrayList<String> result = new ArrayList<String>();
         Iterator<String> it = list.get(list.size()-1).iterator();
         while(it.hasNext())
            result.add(it.next());
         return result;
     }
      
     private void generateParentheses(int number,ArrayList<Set<String>> list,Set<String> parentheses){
         if(number==1){
             parentheses.add("()");
             return;
         }
         StringBuilder sb = new StringBuilder();
         for(String s:list.get(number-2)){
              sb.append("(");
              sb.append(s);
              sb.append(")");
              parentheses.add(sb.toString());
              sb.setLength(0);
         }
     }
}
http://www.programcreek.com/2014/01/leetcode-generate-parentheses-java/

public List<String> generateParenthesis(int n) {
 ArrayList<String> result = new ArrayList<String>();
 ArrayList<Integer> diff = new ArrayList<Integer>();
 
 result.add("");
 diff.add(0);
 
 for (int i = 0; i < 2 * n; i++) {
  ArrayList<String> temp1 = new ArrayList<String>();
  ArrayList<Integer> temp2 = new ArrayList<Integer>();
 
  for (int j = 0; j < result.size(); j++) {
   String s = result.get(j);
   int k = diff.get(j);
 
   if (i < 2 * n - 1) {
    temp1.add(s + "(");
    temp2.add(k + 1);
   }
 
   if (k > 0 && i < 2 * n - 1 || k == 1 && i == 2 * n - 1) {
    temp1.add(s + ")");
    temp2.add(k - 1);
   }
  }
 
  result = new ArrayList<String>(temp1);
  diff = new ArrayList<Integer>(temp2);
 }
 return result;
}

X. DFS
Same idea, but instead of expensive string concatenation, I used StringBuilder and backtrack when necessary, mainly for efficiency.
public List<String> generateParenthesis(int n) {
     List<String> res = new ArrayList<>();
     helper(res, new StringBuilder(), 0, 0, n);
     return res;
}

private void helper(List<String> res, StringBuilder sb, int open, int close, int n) {
    if(open == n && close == n) {
        res.add(sb.toString());
        return;
    }
    
    if(open < n) {
        sb.append("(");
        helper(res, sb, open+1, close, n);
        sb.setLength(sb.length()-1);
    } 
    if(close < open) {
        sb.append(")");
        helper(res, sb, open, close+1, n);
        sb.setLength(sb.length()-1);
    }
}
X. DFS+Cache
https://discuss.leetcode.com/topic/33127/java-easy-to-understand-recursive-dp-method-with-explanations
For each valid parenthesis, there must be a pair whose right parenthesis is at the rightmost location. Thus, a valid parenthesis has to be of the following form:
* ( * )
where * denotes the remaining parentheses which are don't yet know (* can be empty, i.e., with 0 pair of parenthesis). However, we do know the following two important facts:
  • both two * are valid parentheses;
  • they don't overlap at all! (a pair has to be either on the left side or inside (), but cannot be the case where ( is on the left side and ) is inside ())
If we put i parentheses inside (), there are n-i-1 to be put on the left side. This gives us a recursive formula as below:
P(n) = P(n-i-1) x P(i)
where P(n) are all valid parentheses with n parentheses.

public List<String> generateParenthesis(int n) {
 List<String>[] lists = new LinkedList[n+1]; // store all P(k)'s for k=0,1,...,n
 return helper(n, lists);
}

private List<String> helper(int n, List<String>[] lists) {
 if(lists[n]!=null) return lists[n]; // if computed, reuse
 List<String> res = new LinkedList<String>();
 if(n<=0) {
  lists[0] = new LinkedList<String>(Arrays.asList(""));
  return lists[0];
 }
 else if(n==1) {
  lists[1] = new LinkedList<String>(Arrays.asList("()"));
  return lists[1];
 }
 // the following simply implements the recursive formula derived above
    for(int i=0; i<=n-1; i++) {
     List<String> left = helper(n-i-1, lists);
     List<String> inside = helper(i, lists);
     for(String str1 : left) {
      for(String str2 : inside) {
       res.add(str1 + "(" + str2 + ")");
      }
     }
    }
    lists[n] = res; // store computed results for reuse
    return res;
}
public List<String> generateParenthesis(int n) {
 List<String> result = new ArrayList<String>();
 if (n == 0) {
  result.add("");
 } else {
  for (int i = n - 1; i >= 0; i--) {
   List<String> insertSub = generateParenthesis(i);
   List<String> tailSub = generateParenthesis(n - 1 - i);
   for (String insert : insertSub) {
    for (String tail : tailSub) {
     result.add("(" + insert + ")" + tail);
    }
   }

  }
 }
 return result;
}
https://fullengineer.wordpress.com/2015/05/18/generate-parentheses-leetcode/
Use DFS to generate parentheses. We need to keep track of number of ‘(‘ and number of ‘)’ .
Always generate ‘(‘ first and then ‘)’ . And if number of ‘(‘ has to be more or equals than number of ‘)’.
Running time complexity is O(n!) . First let’s assume there is no valid parentheses rule. For each position we can either place ( or ) . Running time would be 2^n . Since there is rule, once we put ( in the place , the next position will be limited. So it is n! . ???? incorrect

https://discuss.leetcode.com/topic/23229/java-dfs-way-solution
public List<String> generateParenthesis(int n) 
{
    List<String> result = new LinkedList<String>();
    if (n > 0) generateParenthesisCore("", n, n, result); 
    return result;
}

private void generateParenthesisCore(String prefix, int left, int right, List<String> result)
{
    if (left == 0 && right == 0) result.add(prefix);
    // Has left Parenthesis    
    if (left > 0) generateParenthesisCore(prefix+'(', left-1, right, result);
    // has more right Parenthesis
    if (left < right) generateParenthesisCore(prefix+')', left, right-1, result);
}


给定的n为括号对，所以就是有n个左括号和n个右括号的组合。
按顺序尝试知道左右括号都尝试完了就可以算作一个解。
注意，左括号的数不能大于右括号，要不然那就意味着先尝试了右括号而没有左括号，类似“)(” 这种解是不合法的。
1     public ArrayList<String> generateParenthesis(int n) {  
 2         ArrayList<String> res = new ArrayList<String>();
 3         String item = new String();
 4         
 5         if (n<=0)
 6             return res;  
 7             
 8         dfs(res,item,n,n);  
 9         return res;  
10     }  
11       
12     public void dfs(ArrayList<String> res, String item, int left, int right){ 
13         if(left > right)//deal wiith ")("
14             return;
15             
16         if (left == 0 && right == 0){  
17             res.add(new String(item));  
18             return;  
19         }
20         
21         if (left>0) 
22             dfs(res,item+'(',left-1,right);  
23         if (right>0) 
24             dfs(res,item+')',left,right-1);  
25     } 
Use String builder
    public List<String> generateParenthesis(int n) {
        List<String> result=new ArrayList<String> ();
        if (n<1){
            return result;
        }
        
        int leftNum=n;
        int rightNum=n;
        StringBuffer current=new StringBuffer();
        buildResult(leftNum, rightNum, current, result);
        
        return result;
    }
    
    private void buildResult(int leftNum, int rightNum, StringBuffer current, List<String> result){
        // if both sides number of parenthese equal to 0, then we got an valid result
        if (leftNum==0 && rightNum==0){
            result.add(current.toString());
            return;
        }
        // if number of left Parenthese bigger than 0, then add one left parenthese and 
        // keep builResult from there
        if (leftNum>0){
            current.append('(');
            buildResult(leftNum-1, rightNum, current, result);
            current.deleteCharAt(current.length()-1); // backtrack undo the change
        }
        
        // if number of right parenthese bigger than left, then add one right parenthese and 
        // builResult from there
        if (rightNum>leftNum){
            current.append(')');
            buildResult(leftNum, rightNum-1, current, result);
            current.deleteCharAt(current.length()-1);//\\
        }
        
    }
setLength is cheaper then deleteCharAt
public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); helper(res, new StringBuilder(), 0, 0, n); return res; } private void helper(List<String> res, StringBuilder sb, int open, int close, int n) { if(open == n && close == n) { res.add(sb.toString()); return; } if(open < n) { sb.append("("); helper(res, sb, open+1, close, n); sb.setLength(sb.length()-1); } if(close < open) { sb.append(")"); helper(res, sb, open, close+1, n); sb.setLength(sb.length()-1); } }
If l==r==n, return the current string, where l and r is the number of left and right parentheses, respectively. Actually, if l==n, meaning that we have used up all left parentheses, we can simply append all of the rest of right parentheses and then return the string.

Recursion part:
If l==r<n, we can only append a left parenthesis;
Otherwise, we can append either one.
private void generator(int n, int l, int r, StringBuilder ss, ArrayList<String> resSet) {  
   if (l==n) {  
     while (r++ < n) ss = ss.append(")");  
     resSet.add(ss.toString());  
   } else if (l==r) {  
     generator(n, l+1, r, ss.append('('), resSet);  
   } else {  
     int oldlen = ss.length();  
     generator(n, l+1, r, ss.append('('), resSet);  
     ss = ss.delete(oldlen, ss.length());  
     generator(n, l, r+1, ss.append(')'), resSet);  
   }  
 }  
   
 public ArrayList<String> generateParenthesis(int n) {  
   ArrayList<String> resSet = new ArrayList<String>();  
   generator(n, 0, 0, new StringBuilder(), resSet);  
   return resSet;
 }
Notice that we use StringBuilder rather than String to improve the performance (see discussion here).
Also, since Java methods pass pointers to objects, the content of object may be modified in the method (see discussion here). In the case here, we need to clean up the StringBuilder when we want to append other things.
    private void dfs(int n, int l, int r, StringBuffer sb, List<String> pare){
        if(r > l || l > n || r > n)       return;
        if(l == n && r == n){
            pare.add(new String(sb));
            return;
        }
        sb.append('(');
        dfs(n, l + 1, r, sb, pare);
        sb.deleteCharAt(l + r); // set(length-1, ')')
        sb.append(')');
        dfs(n, l, r + 1, sb, pare);
        sb.deleteCharAt(l + r);
    }
    public void helper(int n, int l, int r, String s, ArrayList<String> result) {
        if (l == n) {
            while (r < n) {
                s += ")";
                r++;
            }
            result.add(s);
            return;
        }
        
        if (l < n) {
            helper(n, l + 1, r, s+"(", result);
        }
        if (r < l) {
            helper(n, l, r + 1, s+")", result);
        }
    }
http://blog.welkinlan.com/2015/04/13/generate-parentheses-leetcode-java/
Use char array
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String>();
        char[] clause = new char[n+n];
        recursiveGeneration(result, 0, 0, n, clause);
        return result;
    }
    
    public void recursiveGeneration(ArrayList<String> result, int left /*how many "(" used*/, int right /*how many ")" used*/, int n, char[] clause){
        //if all "(" and ")" have been used, output the result
        if (left == n && right == n) {
            result.add(new String(clause));
            return;
        }
//if there are available "("s, it is always safe to set "(" at this position.
        if (left < n) {
            clause[left + right] = '(';
            recursiveGeneration(result, left + 1, right, n, clause);
        }
//after we have generated all the results for the "(" case, we could try to put a ")" at this position.
//Only if there are fewer ")"s used than "("s, can we set ")" at this position.
//Otherwise, it's not possible to generate a valid parenthesis afterwards
        if (right < left) {
            clause[left + right] = ')';
            recursiveGeneration(result, left, right + 1, n, clause);
        }
    }
https://leetcode.com/discuss/71960/ms-beats-92%25-submissions-easy-java-space-optimized-solution
Don't need the int i => open, close is enough.
public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); char[] perm = new char[n*2]; perms(n, n, perm, 0, res); return res; } private void perms(int open, int close, char[] perm, int i, List<String> res) { if (i == perm.length) { res.add(new String(perm)); return; } if (open > 0 && close >= open) { perm[i] = '('; perms(open - 1, close, perm, i+1, res); } if (close > 0) { perm[i] = ')'; perms(open, close - 1, perm, i+1, res); } }
https://github.com/Chang-Hu/Algorithm-Practice/blob/master/Generate%20Parentheses.java
Return result list: - creating too many temp list
    public ArrayList<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<String>();
        }
        return helper(n, 0, 0, new StringBuilder());
    }
    
    public ArrayList<String> helper(int n, int l, int r, StringBuilder s) {
        ArrayList<String> result = new ArrayList<String>();
        
        if (l > n || r > n) {
            return result;
        }
        
        if (r == n) {
            result.add(s.toString());
        }
        
        if (l < n) {
            StringBuilder ss = new StringBuilder(s);
            ss.append("(");
            result.addAll(helper(n, l + 1, r, ss));
        }
        
        if (r < l) {
            StringBuilder ss = new StringBuilder(s);
            ss.append(")");
            result.addAll(helper(n, l, r + 1, ss));
        }
        
        return result;
    }

05    vector<string> generateParenthesis (int n) {
06        if (n == 0) return vector<string>(1, "");
07        if (n == 1) return vector<string> (1, "()");
08        vector<string> result;
09
10        for (int i = 0; i < n; ++i)
11            for (auto inner : generateParenthesis (i))
12                for (auto outer : generateParenthesis (n - 1 - i))
13                    result.push_back ("(" + inner + ")" + outer);
14
15        return result;
16    }

05    vector<string> generateParenthesis(int n) {
06        vector<string> result;
07        if (n > 0) generate(n, "", 0, 0, result);
08        return result;
09    }
10    // l 表示 ( 出现的次数, r 表示 ) 出现的次数
11    void generate(int n, string s, int l, int r, vector<string> &result) {
12        if (l == n) {
13            result.push_back(s.append(n - r, ')'));
14            return;
15        }
16        generate(n, s + '(', l + 1, r, result);
17        if (l > r) generate(n, s + ")", l, r + 1, result);
18    }

Write a function to generate all possible n pairs of balanced parentheses.

void printParenthesis(int n)
{
  if(n > 0)
     _printParenthesis(0, n, 0, 0);
  return;
}
void _printParenthesis(int pos, int n, int open, int close)
{
  static char str[MAX_SIZE];    
  if(close == n)
  {
    printf("%s \n", str);
    return;
  }
  else
  {
    if(open > close) {
        str[pos] = '}';
        _printParenthesis(pos+1, n, open, close+1);
    }
    if(open < n) {
       str[pos] = '{';
       _printParenthesis(pos+1, n, open+1, close);
    }
  }
}

EPI Solution

Enumerate strings of balanced parenthesis  GenerateParentheses.java

  public static List<String> generateParentheses(int n) {
    String s = "";
    List<String> result = new ArrayList<>();
    generateParenthesesHelper(2 * n, 0, s, result);
    return result;
  }

  private static void generateParenthesesHelper(int remained, int leftParens,
                                                String s, List<String> result) {
    if (remained == 0) {
      result.add(s);
      return;
    }

    if (leftParens < remained) { // Able to insert '('.
      generateParenthesesHelper(remained - 1, leftParens + 1, s + "(", result);
    }
    if (leftParens > 0) { // Able to insert ')'.
      generateParenthesesHelper(remained - 1, leftParens - 1, s + ")", result);
    }
  }
http://stackoverflow.com/questions/24704170/generate-balanced-parentheses-in-java
public class generateParentheses {
    public static ArrayList<String> generateParenthesis(int n) {

    ArrayList<String> result = new ArrayList<String>();
    StringBuilder sb = new StringBuilder();

    generate(n, 0, 0, result, sb);
    return result;
}

public static void generate(int n, int left, int right, ArrayList<String> result,
        StringBuilder sb) {

    if (left < right) {
        return;
    }
    if (left == n && right == n) {
        result.add(sb.toString());
        //sb.delete(0,sb.length());
        return;
    }
    if (left == n) {
        generate(n, left, right + 1, result, sb.append(')'));
        //delete current ')'.
        sb.delete(sb.length() - 1, sb.length());
        return;
    }

    generate(n, left + 1, right, result, sb.append('('));
    //delete current '(' after you finish using it for next recursion.
    sb.delete(sb.length() - 1, sb.length());
    generate(n, left, right + 1, result, sb.append(')'));
    //same as above here.
    sb.delete(sb.length() - 1, sb.length());
}
X. Using Stack
https://discuss.leetcode.com/topic/1921/does-anyone-come-up-with-a-non-recursion-solution/5
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;
}

X. Misc
https://leetcode.com/discuss/18162/my-accepted-java-solution
For 2, it should place one "()" and add another one insert it but none tail it,
'(' f(1) ')' f(0)
or add none insert it but tail it by another one,
'(' f(0) ')' f(1)
Thus for n, we can insert f(i) and tail f(j) and i+j=n-1,
'(' f(i) ')' f(j)
I think you can add a cache to improve performance; so for the same n, you only need to calculate once.
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<String>();
    if (n == 0) {
        result.add("");
    } else {
        for (int i = n - 1; i >= 0; i--) {
            List<String> insertSub = generateParenthesis(i);
            List<String> tailSub = generateParenthesis(n - 1 - i);
            for (String insert : insertSub) {
                for (String tail : tailSub) {
                    result.add("(" + insert + ")" + tail);
                }
            }

        }
    }
    return result;
}

( ()) -> (()()) I* inserted pair after 1st left paren */
-> ((())) /* ins erted pair after 2nd left paren */
-> ()(()) /* inserted pair at beginning of string*/
() () -> (())() /* inserted pair after 1st left paren */
-> ()(()) /* ins erted pair after 2nd left paren */
-> () () () /* inserted pair at beginning of string*/
But wait-we have some duplicate pairs listed. The string () ( ()) is listed twice.
-- We waste a lot of time coming up with the duplicate strings.
Set<String> generateParens (int remaining) {
        Set<String> set= new HashSet<String>();
        if (remaining== 0) {
                set.add("");
        } else {
                Set<String> prev = generateParens(remaining - 1);
                for (String str : prev) {
                        for (int i= 0; i < str.length(); i++) {
                                if (str.charAt(i) == '(') {
                                        String s = insertlnside(str, i);
                                        /*Add s to set if it's not already in there. Note: HashSet
                                         * automatically checks for duplicates before adding, so an explicit
                                         * check is not necessary. */
                                        set.add(s);
                                }
                        }
                        set.add("()" + str);
                }
        }
        return set;
}

String insertlnside(String str, int leftlndex) {
        String left = str.substring(0, leftlndex + 1);
        String right = str.substring(leftindex + 1, str.length());
        return left + "()" + right;
}

X.
void addParen(Arraylist<String> list, int leftRem, int rightRem, char[] str,
              int index) {
        if (leftRem < 0 || rightRem < leftRem) return; // invalid state

        if (leftRem == 0 && rightRem == 0) {/*Out of left and right parentheses */
                list.add(String.valueOf(str));
        } else {
                str[index] = '('; // Add left and recurse
                addParen(list, leftRem - 1, rightRem, str, index + 1);

                str[index] = ')'; // Add right and recurse
                addParen(list, leftRem, rightRem - 1, str, index + 1);
        }
}

ArrayList<String> generateParens(int count) {
        char[] str = new char[count *2];
        Arraylist<String> list = new Arraylist<String>();
        addParen(list, count, count, str, 0);
        return list;
}
X. BFS
https://discuss.leetcode.com/topic/1921/does-anyone-come-up-with-a-non-recursion-solution/10
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];
}
https://leetcode.com/discuss/25063/easy-to-understand-java-backtracking-solution
-- Waste too much space

public List<String> generateParenthesis(int n) { List<List<String>> lists = new ArrayList<>(); lists.add(Collections.singletonList("")); for (int i = 1; i <= n; ++i) { final List<String> list = new ArrayList<>(); for (int j = 0; j < i; ++j) { for (final String first : lists.get(j)) { for (final String second : lists.get(i - 1 - j)) { list.add("(" + first + ")" + second); } } } lists.add(list); } return lists.get(lists.size() - 1); }

X. https://leetcode.com/articles/generate-parentheses/
Approach 3: Closure Number
Intuition
To enumerate something, generally we would like to express it as a sum of disjoint subsets that are easier to count.co
Consider the closure number of a valid parentheses sequence S: the least index >= 0 so that S[0], S[1], ..., S[2*index+1] is valid. Clearly, every parentheses sequence has a unique closure number. We can try to enumerate them individually.
Algorithm
For each closure number c, we know the starting and ending brackets must be at index 0 and 2*c + 1. Then, the 2*c elements between must be a valid sequence, plus the rest of the elements must be a valid sequence.
  public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList();
    if (n == 0) {
      ans.add("");
    } else {
      for (int c = 0; c < n; ++c)
        for (String left : generateParenthesis(c))
          for (String right : generateParenthesis(n - 1 - c))
            ans.add("(" + left + ")" + right);
    }
    return ans;

  }

We can generate all 2^{2n} sequences of '(' and ')' characters. Then, we will check if each one is valid.
Algorithm
To generate all sequences, we use a recursion. All sequences of length n is just '(' plus all sequences of length n-1, and then ')' plus all sequences of length n-1.
To check whether a sequence is valid, we keep track of balance, the net number of opening brackets minus closing brackets. If it falls below zero at any time, or doesn't end in zero, the sequence is invalid - otherwise it is valid
  • Time Complexity : O(2^{2n}n). For each of 2^{2n} sequences, we need to create and validate the sequence, which takes O(n) work.
  • Space Complexity : O(2^{2n}n). Naively, every sequence could be valid. See Approach 3 for development of a tighter asymptotic bound
  public List<String> generateParenthesis(int n) {
    List<String> combinations = new ArrayList();
    generateAll(new char[2 * n], 0, combinations);
    return combinations;
  }

  public void generateAll(char[] current, int pos, List<String> result) {
    if (pos == current.length) {
      if (valid(current))
        result.add(new String(current));
    } else {
      current[pos] = '(';
      generateAll(current, pos + 1, result);
      current[pos] = ')';
      generateAll(current, pos + 1, result);
    }
  }

  public boolean valid(char[] current) {
    int balance = 0;
    for (char c : current) {
      if (c == '(')
        balance++;
      else
        balance--;
      if (balance < 0)
        return false;
    }
    return (balance == 0);

  }


at
Labels: , , , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts