【重点】【回溯】22.括号生成

Allenlzcoder

已于 2025-06-04 00:29:11 修改

阅读量415

点赞数 9

分类专栏：力扣Top100 文章标签：深度优先括号生成

于 2023-12-19 00:35:56 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135074585

版权

力扣Top100 专栏收录该内容

100 篇文章

订阅专栏

本文介绍了如何使用深度优先搜索（DFS）算法在Java中解决生成n对括号的所有可能组合问题，通过递归方法和字符数组tmp进行状态跟踪。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

法1：DFS

注意：path 长度是固定的，直接覆盖就行，不需要恢复现场。如果 path 初始化成空列表，就需要恢复现场。

Python

## 最佳写法
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = list()
        tmp = ['']*(2*n) 
        self.dfs(0, 0, 0, tmp, res, n)
        return res
    
    def dfs(self, idx, left_count, right_count, tmp, res, n):
        if (left_count < right_count or left_count > n or right_count > n):
            return
        if idx == n * 2:
            res.append(''.join(tmp))
            return

        if left_count > right_count:
            tmp[idx] = '('
            self.dfs(idx+1, left_count+1, right_count, tmp, res, n)
            tmp[idx] = ')'
            self.dfs(idx+1, left_count, right_count+1, tmp, res, n)
        else:
            tmp[idx] = '('
            self.dfs(idx+1, left_count+1, right_count, tmp, res, n)

## 写法2
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = list()
        tmp = list()
        self.dfs(0, 0, 0, tmp, res, n)
        return res
    
    def dfs(self, idx, left_count, right_count, tmp, res, n):
        if (left_count < right_count or left_count > n or right_count > n):
            return
        if len(tmp) == n * 2:
            res.append(''.join(tmp))
            return

        if left_count > right_count:
            tmp.append('(')
            self.dfs(idx+1, left_count+1, right_count, tmp, res, n)
            tmp.pop()
            tmp.append(')')
            self.dfs(idx+1, left_count, right_count+1, tmp, res, n)
            tmp.pop() # 回溯, 为了还原现场需要删除!!!
        else:
            tmp.append('(')
            self.dfs(idx+1, left_count+1, right_count, tmp, res, n)
            tmp.pop() # 回溯, 为了还原现场需要删除!!!

Java

必须掌握的方法！

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] tmp = new char[n * 2];
        dfs(0, 0, 0, tmp, res);

        return res;
    }

    public void dfs(int curIndex, int left, int right, char[] tmp, List<String> res) {
        if (left < right || left > tmp.length / 2 || right > tmp.length / 2) {
            return;
        }
        if (curIndex == tmp.length) {
            res.add(String.valueOf(tmp));
            return;
        }

        if (left > right) {
            tmp[curIndex] = '(';
            dfs(curIndex + 1, left + 1, right, tmp, res);
            tmp[curIndex] = ')';
            dfs(curIndex + 1, left, right + 1, tmp, res);
        } else if (left == right) {
            tmp[curIndex] = '(';
            dfs(curIndex + 1, left + 1, right, tmp, res);
        }
    }
}