2ms Java solution with explanation and sane variable names

  • 0


    Every string must begin with an open parenthesis, which is why our initial call to generate uses nOpenUsed = 1, nClosedUsed = 0, and the StringBuilder sb is constructed with "(".

    Given a valid partially-built string:

    • If the string has used all available open and closed parentheses, then the string is actually complete and we add it to the output list;
    • Otherwise,
      • We can add a close parenthesis at the end whenever we have used fewer close parentheses than open parentheses so far.
      • We can add an open parenthesis at the end so long as we haven't used all of them already.


    public List<String> generateParenthesis(int n) {
         List<String> outputList = new ArrayList<>();
         generate(n, 1, 0, new StringBuilder("("), outputList);
         return outputList;
     private void generate(int numPairs, int nOpenUsed, int nClosedUsed, StringBuilder sb, List<String> outputList) {
         if (nOpenUsed == numPairs && nClosedUsed == numPairs) {
         if (nOpenUsed > nClosedUsed) {
             StringBuilder sb2 = (nOpenUsed < numPairs) ? new StringBuilder(sb) : sb;
             generate(numPairs, nOpenUsed, nClosedUsed + 1, sb2, outputList);
         if (nOpenUsed < numPairs) {
             generate(numPairs, nOpenUsed + 1, nClosedUsed, sb, outputList);

Log in to reply

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