Java DFS way solution


  • 38
    M
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        generateOneByOne("", list, n, n);
        return list;
    }
    public void generateOneByOne(String sublist, List<String> list, int left, int right){
        if(left > right){
            return;
        }
        if(left > 0){
            generateOneByOne( sublist + "(" , list, left-1, right);
        }
        if(right > 0){
            generateOneByOne( sublist + ")" , list, left, right-1);
        }
        if(left == 0 && right == 0){
            list.add(sublist);
            return;
        }
    }

  • 9
    J

    Thanks for your idea, I rewrite a little bit, basically simplify the logic in comparing left and right.
    For other readers, this is a top-down recursion solution. AFAIK, this is faster than the bottom-up recursion solution.

    public List<String> generateParenthesis(int n) 
    {
        List<String> result = new LinkedList<String>();
        if (n > 0) generateParenthesisCore("", n, n, result); 
        return result;
    }
    
    private void generateParenthesisCore(String prefix, int left, int right, List<String> result)
    {
        if (left == 0 && right == 0) result.add(prefix);
        // Has left Parenthesis    
        if (left > 0) generateParenthesisCore(prefix+'(', left-1, right, result);
        // has more right Parenthesis
        if (left < right) generateParenthesisCore(prefix+')', left, right-1, result);
    }

  • 5
    H

    Could you please explain a little bit on how you came up with this solution? would be helpful for learners. Thanks...


  • 0
    E

    very nice solution!


  • 0
    M
    This post is deleted!

  • 0

    @Jason_Weng Your solution seems easier to understand. Thanks for sharing.


  • 0
    Y

    @Jason_Weng said in Java DFS way solution:

    top-down recursion solution. AFAIK, this is faster than the bottom-up

    Hi @Jason_Weng Why is it a "top-down" recursion rather than the bottom-up? Many thanks!


  • 0
    Y

    can you explain why there is no duplicated in the result?


  • 0
    V

    I dont understand how the code doesn't stop with printing ((())) for input 3. When the last return is reached where does it return to?


  • 0
    C

    @vvamsa I have the same question...


  • 2
    K

    I really have no idea about the running process of this code, I just think the result is "((()))",


Log in to reply
 

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