Java Binary Tree Solution


  • 0
    J

    This problem is like a binary tree. You only have two options -- left parenthesis and right parenthesis. Besides that, you also have a constrain that right parenthesis can not more than left parenthesis. The leaves are the result.

    In my solution, l represents the number of left parenthesis and the r is the number of right parenthesis. l >= r is the constrain mentioned above.

               n = 2
                root
                 /
                (
             /     \
           ((       () 
             \      /
             (()   ()(
               \    \
              (())  ()()
    
    public class GenerateParentheses {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            generateSemi(res, n, n, "");
            return res;
        }
    
        private void generateSemi(List<String> res, int l, int r, String str){
            if(l < 0 || r < l) return;
            if(l == 0 && r == 0){
                res.add(str);
                return;
            }
            if(l > 0) generateSemi(res, l - 1, r, str + "(");
            if(r > 0) generateSemi(res, l, r - 1, str + ")");
        }
    }
    

Log in to reply
 

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