22. Generate Parentheses

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Constraints

• 1 <= n <= 8

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: n = 3

Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2

Input: n = 1

Output: ["()"]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        recursive(result, n, n, "");
        return result;
    }
    
    public void recursive(List<String> result, int l, int r, String comb) {
        if(l > r) return;
        if(l == 0 && r == 0) {
            result.add(comb);
            return;
        }
        if(l > 0) {
            recursive(result, l-1, r, comb+"(");
        }
        if(r > 0) {
            recursive(result, l, r-1, comb+")");
        }
    }
}

Follow up