Easy to understand Java backtracking solution


  • 250
    B
     public List<String> generateParenthesis(int n) {
            List<String> list = new ArrayList<String>();
            backtrack(list, "", 0, 0, n);
            return list;
        }
        
        public void backtrack(List<String> list, String str, int open, int close, int max){
            
            if(str.length() == max*2){
                list.add(str);
                return;
            }
            
            if(open < max)
                backtrack(list, str+"(", open+1, close, max);
            if(close < open)
                backtrack(list, str+")", open, close+1, max);
        }
    

    The idea here is to only add '(' and ')' that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a '(' we will then discard it and try a ')' which can only close a valid '('. Each of these steps are recursively called.


  • 24
    K

    The most easy to understand and concise code. Thanks so much ! I need to practice more :( .


  • 0
    X

    It is better to use LinkedList for the efficiency.


  • 0
    L

    Easy to understand. Thanks for sharing


  • 0
    M

    Brilliant solution, helped me a lot, thank you for sharing.


  • 6
    H

    I am trying to figure it out. What is the time complexity?


  • 0
    H

    I like this idea.


  • 0
    M

    Brilliant idea! Most easy to understand!


  • 0
    Y

    What is the runtime of this? 2^n??


  • 1
    M

    This is not the right answer. For example, when n = 1, if(open < max) return '()', however, next if(close < max) will still add ')(' to the list.

    if(right < max && right < left){
    backtrack(arr, str + ')', left, right + 1, max);
    }
    if(left < max){
    backtrack(arr, str+'(', left + 1, right, max);
    }

    this will work.


  • 5
    R

    This solution is easy to understand. But I think it's not a backtracking solution?


  • 4
    O

    close < open not close < max


  • 29
    Y

    Same idea, but instead of expensive string concatenation, I used StringBuilder and backtrack when necessary, mainly for efficiency.

    public List<String> generateParenthesis(int n) {
         List<String> res = new ArrayList<>();
         helper(res, new StringBuilder(), 0, 0, n);
         return res;
    }
    
    private void helper(List<String> res, StringBuilder sb, int open, int close, int n) {
        if(open == n && close == n) {
            res.add(sb.toString());
            return;
        }
        
        if(open < n) {
            sb.append("(");
            helper(res, sb, open+1, close, n);
            sb.setLength(sb.length()-1);
        } 
        if(close < open) {
            sb.append(")");
            helper(res, sb, open, close+1, n);
            sb.setLength(sb.length()-1);
        }
    }

  • 3
    F

    why do you need sb.setLength(sb.length()-1); ?


  • 3
    Q

    Hi all,

    My solution is much similar, except that I'm using a char array for efficiency.
    It also allowed me to pass less variables into the function (because we can use the length of char array).

    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result = new LinkedList<>();
            char[] sample = new char[2*n];
            generate(sample, 0, 0, result);
            return result;
        }
        
        private void generate(char[] s, int open, int closed, List<String> result) {
            if (open + closed == s.length) {
                result.add(new String(s));
                return;
            }
            if (open < s.length/2) {
                s[open+closed] = '(';
                generate(s, open+1, closed, result);
            }
            if (open > closed) {
                s[open+closed] = ')';
                generate(s, open, closed+1, result);
            }
        }
    }

  • 0
    F

    For example, in a case such that we could append both "(" and ")", after appending "(" we need to remove it before appending ")" later.


  • 1

    Very clear, but hard to come up by myself!


  • 1
    Y

    can you explains why it is correct for there is no missed or duplicated?


  • 2
    Z

    You forgot to delete the last char during backtracking.


  • 0
    M

    @quoma If using LinkedList, since order doesn't matter, use addFirst(). add is O(n) and addFirst is O(1).


Log in to reply
 

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