JohnShen's Blog.

[Leetcode单排] 括号生成 (N22)

backtracking dfs search
字数统计: 262阅读时长: 1 min
2019/07/29 Share

22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

给出一个整数 n，给出 n 对左右括号所有可能的排列结果。

设左右括号的个数分别为left和right，则需要满足以下规律：left <= n && right <= right。所以在每一次递归中需要考虑两种变量的变化。以 left = 2, right = 0为例， 满足第一个条件，则求解handle(3,3,0,"(((", result)分支下所有满足条件的情况，之后再考虑handle(3,2,1,"(()", result)分支下所有满足条件结果。两个情况只要满足条件都要进行。

答案虽然比较短，但还是需要仔细咀嚼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    handle(n, 0, 0, "", result);
    return result;
}

private void handle(int n, int left, int right, String cur, List<String> result) {
    if (left == n && right == n) {
        result.add(cur);
        return;
    }
    if (left < n) {
        handle(n, left + 1, right, cur + "(", result);
    }
    if (right < left) {
        handle(n, left, right + 1, cur + ")", result);
    }
}
CATALOG
  1. 1. 22. Generate Parentheses
Total : 64
2021
2020
2019
clickhouse clojure DDIA, 数据库 docker DDIA greenplum connection-pool db spark concurrent jvm backtracking permutations dfs search bfs combination tree partition monitor cpu memory redis network cache spring micrometer prometheus
db clojure 分布式 docker java k8s leetcode linux-docker-monitor linux 缓存 BigData 经济学 java-monitor monitor