[Leetcode][22. 括号生成] 3种方法：暴力法，回溯法，DP

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 22. 括号生成 题解。

方法一：暴力法

思路与算法：

直接生成所有 \(2^{2n}\) 个’(‘和’)’字符构成的序列，然后我们检查每一个是否有效即可。

为了生成所有序列，我们可以使用递归。长度为 \(n\) 的序列就是在长度为 \(n-1\) 的序列前加一个’(‘或’)’。

为了检查序列是否有效，我们遍历这个序列，并使用一个变量 \(balance\) 表示左括号的数量减去右括号的数量。如果在遍历过程中 \(balance\) 的值小于零，或者结束时 \(balance\) 的值不为零，那么该序列就是无效的，否则它是有效的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public List<String> generateParenthesis(int n) {
	if (n < 1) {
		return new ArrayList<>();
	}

	List<String> ans = new ArrayList<>();
	generateAll(new char[2 * n], 0, ans);
	return ans;
}

public void generateAll(char[] current, int pos, List<String> result) {
	if (pos == current.length) {
		if (valid(current)) {
			result.add(new String(current));
		}
	} else {
		current[pos] = '(';
		generateAll(current, pos + 1, result);
		current[pos] = ')';
		generateAll(current, pos + 1, result);
	}
}

public boolean valid(char[] current) {
	int balance = 0;
	for (char c : current) {
		if (c == '(') {
			++balance;
		} else {
			--balance;
		}
		if (balance < 0) {
			return false;
		}
	}
	return balance == 0;
}

复杂度分析

  • 时间复杂度：\(O(2^{2n}n)\)，对于 \(2^{2n}\) 个序列中的每一个，我们用于建立和验证该序列的复杂度为 \(O(n)\)。

  • 空间复杂度：\(O(n)\)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 \(O(1)\) 的空间，最多递归 \(2n\) 层，因此空间复杂度为 \(O(n)\)。

方法二：回溯法

思路与算法：

其实这道题是回溯法的经典练习题，吃透这道题，可以学会解决任何类似回溯题。

方法一没有做剪枝处理，所以造成计算量太大。我们可以只在序列仍然保持有效时才添加’(’ or ‘)’，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果左括号数量不大于 \(n\)，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<String> generateParenthesis(int n) {
	if (n < 1) {
		return new ArrayList<>();
	}

	List<String> ans = new ArrayList<>();
	backtrace(ans, new StringBuilder(), 0, 0, n);
	return ans;
}

public void backtrace(List<String> ans, StringBuilder sb, int left, int right, int num) {
	if (left == right && left == num) {
		ans.add(sb.toString());
		return;
	}

	if (left < right || left > num || right > num) {
		return;
	}

	sb.append('(');
	backtrace(ans, sb, left + 1, right, num);
	sb.deleteCharAt(sb.length() - 1);

	sb.append(')');
	backtrace(ans, sb, left, right + 1, num);
	sb.deleteCharAt(sb.length() - 1);
}

复杂度分析

  • 时间复杂度：\(O(\frac{4^n}{\sqrt{n}})\)，在回溯过程中，每个答案需要 \(O(n)\) 的时间复制到答案数组中。

  • 空间复杂度：\(O(n)\)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 \(O(1)\) 的空间，最多递归 \(2n\) 层，因此空间复杂度为 \(O(n)\)。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗