LeetCode 22. 括号生成

题目描述

🔥 22. 括号生成

思路分析

  1. 定义一个辅助函数，该函数使用回溯法生成括号组合。
  2. 回溯函数需要三个参数：当前生成的括号组合字符串 current，左括号的数量 left，和右括号的数量 right。
  3. 在回溯的过程中，有两个关键条件：
    • 如果 left 和 right 都等于 n，表示已经生成了一个有效的括号组合，将其添加到结果列表中。
    • 如果 left 小于 n，可以添加一个左括号，并继续回溯。
    • 如果 right 小于 left，可以添加一个右括号，并继续回溯。
  4. 递归结束条件是 left 和 right 都等于 n。
  5. 在主函数中，创建一个空的结果列表，然后调用回溯函数开始生成括号组合。
  6. 最后，返回结果列表作为答案。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func generateParenthesis(n int) []string {
	res := make([]string, 0)
	dfs(n, n, "", &res)
	return res
}

func dfs(lc, rc int, path string, res *[]string) {
	if lc == 0 && rc == 0 {
		*res = append(*res, path)
		return
	}
	if lc > 0 {
		dfs(lc-1, rc, path+"(", res)
	}
	if rc > lc {
		dfs(lc, rc-1, path+")", res)
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func generateParenthesis(n int) []string {
	var result []string
	backtrack("", 0, 0, n, &result)
	return result
}

func backtrack(current string, left, right, n int, result *[]string) {
	if left == n && right == n {
		*result = append(*result, current)
		return
	}

	if left < n {
		backtrack(current+"(", left+1, right, n, result)
	}

	if right < left {
		backtrack(current+")", left, right+1, n, result)
	}
}

🍏 点击查看 Java 题解

1

write your code here

相似题目

题目 难度 题解
电话号码的字母组合 Medium  
有效的括号 Easy  
本文作者:
本文链接: https://hgnulb.github.io/blog/55185444
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！