SHARE
TWEET

Untitled

a guest Oct 24th, 2017 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class GenerateParentheses {
  2.     /*
  3.     This solution is simple and clear.
  4.     In the dfs() method, left stands for the current number of (, right stands for the current number of ).
  5.  
  6.     如何保证这个combination是well-formed?在插入过程中的任何时候:
  7.     1. 只要"("的数量没有超过n,都可以插入"("。
  8.     2. 而可以插入")"的前提则是当前的"("数量必须要多余当前的")"数量。
  9.      */
  10.  
  11.     public List<String> generateParenthesis(int n) {
  12.         List<String> ans = new LinkedList<>();
  13.         dfs("", 0,0, n, ans);
  14.         return ans;
  15.     }
  16.  
  17.     private void dfs(String str, int left, int right, int n, List<String> ans){
  18.         if(str.length()==2*n){
  19.             ans.add(str);
  20.             return;
  21.         }
  22.         if(left<n){
  23.             dfs(str+"(", left+1, right, n, ans);
  24.         }
  25.         if(right<left){
  26.             dfs(str+")", left, right+1, n, ans);
  27.         }
  28.     }
  29. }
RAW Paste Data
Top