-
Notifications
You must be signed in to change notification settings - Fork 13
/
Backtracking_GenerateAllPossibleParentheses.java
50 lines (44 loc) · 1.79 KB
/
Backtracking_GenerateAllPossibleParentheses.java
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
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
// https://practice.geeksforgeeks.org/problems/generate-all-possible-parentheses/1
// https://leetcode.com/problems/generate-parentheses/
// https://leetcode.com/problems/generate-parentheses/discuss/10100/Easy-to-understand-Java-backtracking-solution
// https://www.youtube.com/watch?v=I9GxNZBLYdk&t=128s (great recursion tree visualization and explanation)
// https://www.youtube.com/results?search_query=Generate+balanced+bracket+combinations
public class Backtracking_GenerateAllPossibleParentheses {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
while (t-->0) {
int n = Integer.parseInt(br.readLine().trim());
List<String> output = allParenthesis(n);
StringBuilder sb = new StringBuilder();
for (String str : output) {
sb.append(str + "\n");
}
System.out.print(sb);
sb.setLength(0);
}
}
public static List<String> allParenthesis(int n)
{
List<String> output = new ArrayList<>();
backtracking(output, "", 0, 0, n);
return output;
}
private static void backtracking(List<String> output, String currStr, int open, int close, int max) {
if(currStr.length() == max*2) {
output.add(currStr);
return;
}
if(open < max) {
backtracking(output, currStr + "(", open + 1, close, max);
}
if(close < open) {
backtracking(output, currStr + ")", open, close + 1, max);
}
}
}