LeetCode 22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

問題を分析する、可能な範囲でオーダーを減らす

class Solution {
    public List<String> generateParenthesis(int n) {
        //1 -> "()"
        //2 -> "(())", "()()"
        //3 -> "()()()", "(())()", "()(())", "((()))", "(()())"
        
        //invalid: ")))(((", "))(())" ...etc
        
        // policy1: generated all possible and check each case
        // policy2: when add a ')', then check balance with '(' 
           //want to avoid ')(' or '())()'
           //number of ')' is never bigger than '('
        //since policy 1 has more complicated time complexity, we take policy2
        
        List<String> answer = new ArrayList<>();
        findAnswer(n, 0, 0, new StringBuilder(), answer);
        return answer;
    }
    
    private void findAnswer(int n, int start, int end, StringBuilder current, List<String> answer){
        if (start == end && end == n){
            answer.add(new String(current));
            return;
        }
        
        //take start
        if (start < n){
            current.append("(");
            findAnswer(n, start + 1, end, current, answer);
            current.setLength(current.length() - 1);
        }
        
        if (end < n && end < start){
            current.append(")");
            findAnswer(n, start, end + 1, current, answer);
            current.setLength(current.length() - 1);
        }
    }
}