1 ms (beats 92% of submissions) easy Java space-optimized solution


  • 8
    A
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] perm = new char[n*2];
        perms(n, n, perm, 0, res);
        return res;
    }
    
    private void perms(int open, int close, char[] perm, int i, List<String> res) {
        if (i == perm.length) {
            res.add(new String(perm));
            return;
        }
        if (open > 0 && close >= open) {
            perm[i] = '(';
            perms(open - 1, close, perm, i+1, res);
        }
        if (close > 0) {
            perm[i] = ')';
            perms(open, close - 1, perm, i+1, res);
        }
    }

  • 0
    C

    nice idea !!!


  • 0
    T

    The safety condition if (!(open == 0 && close == 0)) return; is never executed. I guess it's just input validation for first call, because if the args to first call are valid, then all the recursive calls are valid too; right?


  • 0
    A

    Good catch, it's not used. Even for the first call the i >= perm.length should fail, so it's still not used. I will remove it. Thanks for noticing!


  • 0
    T

    Just saw that >= is also paranoid, == should be sufficient for this solution. i cannot get bigger because i == length will shortcut and prevent the i+1 call.


  • 0
    A

    Agree, thanks for code review :)


  • 0
    T

    Can you explain how you interpret close >= open?


  • 0
    P

    means we can not close more parentheses than we have opened


  • 0
    A

    "means we can not close more parentheses than we have opened" yes, exactly, there is no need to continue the recursion if there are not enough open parenthesis, e.g. "()))"


Log in to reply
 

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