[알고리즘]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:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

backtracking

class Solution {     public List<String> generateParenthesis(int n) {         List<String> result = new ArrayList<>();         backtrack(result, "", 0 , 0, n);         return result;     }          public void backtrack(List<String> result, String cur, int open, int close, int max) {         System.out.println(cur + ", oepn : " + open + ", close : " + close);         if (cur.length() == max * 2) {             result.add(cur);             return;         }                  if (open < max) {             backtrack(result, cur+"(" , open+1, close, max);         }                          if (close < open) {             backtrack(result, cur+")", open, close+1, max);         }            } } Colored by Color Scripter

, oepn : 0, close : 0
(, oepn : 1, close : 0
((, oepn : 2, close : 0
(((, oepn : 3, close : 0
(((), oepn : 3, close : 1
((()), oepn : 3, close : 2
((())), oepn : 3, close : 3
((), oepn : 2, close : 1
(()(, oepn : 3, close : 1
(()(), oepn : 3, close : 2
(()()), oepn : 3, close : 3
(()), oepn : 2, close : 2
(())(, oepn : 3, close : 2
(())(), oepn : 3, close : 3
(), oepn : 1, close : 1
()(, oepn : 2, close : 1
()((, oepn : 3, close : 1
()((), oepn : 3, close : 2
()(()), oepn : 3, close : 3
()(), oepn : 2, close : 2
()()(, oepn : 3, close : 2
()()(), oepn : 3, close : 3