Recursive Java Solution 2ms


  • 0
    M

    The basic idea is to store the number of '(' and ')'. Placing a '(' will decrease the number of '(' by one but increase the number of ')' by one.

    public class Solution {
        private void helper(int n, int cnt, List<String> res, StringBuilder sb) {
            if (n==0 && cnt==0) {
                res.add(sb.toString());
                return;
            }
            
            if (n > 0) {
                helper(n-1, cnt+1, res, sb.append('('));
                sb.deleteCharAt(sb.length()-1);
            }
            
            if (cnt > 0) {
                helper(n, cnt-1, res, sb.append(')'));
                sb.deleteCharAt(sb.length()-1);
            }
        }
        
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList();
            helper(n, 0, res, new StringBuilder());
            return res;
        }
    }
    

Log in to reply
 

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