Untitled

 avatar
unknown
plain_text
2 months ago
1.1 kB
3
Indexable
class Solution {
    List<String> res;

    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        sb.append("(");
        int leftCount = n-1, rightCount = n;

        backtracking(sb, leftCount, rightCount);
        return res;
    }

    void backtracking(StringBuilder sb, int leftCount, int rightCount) {
        if (rightCount < leftCount) return;

        if (leftCount == 0 && rightCount == 0) {
            // for (int i = 0; i < rightCount; i++) {
            //     sb.append(")");
            // }
            res.add(sb.toString());
            return;
        }

        if (leftCount > 0) {
            sb.append("("); leftCount--;
            backtracking(sb, leftCount, rightCount);
            sb.delete(sb.length()-1, sb.length()); leftCount++;
        }
        
        if (rightCount > 0) {
            sb.append(")"); rightCount--;
            backtracking(sb, leftCount, rightCount);
            sb.delete(sb.length()-1, sb.length()); rightCount++;
        }
    }
}
Editor is loading...
Leave a Comment