Easy Java Solution


  • 0
    I
    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> list = new ArrayList<String>();
            backtrace(0, n, list, "");
            return list;
        }
        
        private void backtrace(int stack, int remain, List<String> list, String str) {
            if(stack == 0 && remain == 0) {
                list.add(str);
                return;
            }
            if(stack != 0) {
                backtrace(stack-1, remain, list, str+")"); //pop to match ')'
            }
            if(remain != 0) {
                backtrace(stack+1, remain-1, list, str+"("); //push  '(' into stack , and the size of stack increase
            }
        }
    }
    

    It first comes to me that I can use a stack to match the parentheses, I can push '(' into stack and pop it to match ')'. I use remain here to indicate how many '(' left to push into stack. As the stack only store the same value which is '(‘, I can use a integer to indicate the size of stack instead of using the real stack.


Log in to reply
 

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