Generate Parentheses

Problem Id: 22 Difficulty: Medium Tag: String Tag: Backtracking


Intuition

Use a DFS to search all possible results.

Solution


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        return self._helper(0, 0, n)

    def _helper(self, left, right, total):
        if left == right == total:
            return [""]

        res = []
        if left < total:
            res.extend(["(" + s for s in self._helper(left + 1, right, total)])
        if right < total and right < left:
            res.extend([")" + s for s in self._helper(left, right + 1, total)])
        return res