Leetcode22

DFS

参数的subAns每次都使用新的字符串，回溯时无需修改
当右括号的剩余数量大于左括号剩余数量时肯定时错误答案，这个分支可以去除

import java.util.ArrayList;
import java.util.List;/*** 使用另一种终结条件，依旧是dfs*/
public class Solution {
    public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList<>();if(n == 0)return ans;dfs(ans,"",0,0,n);return ans;}public void dfs(List<String> ans,String subAns,int left,int right,int n){
    //终止循环条件if(left == n && right == n){
    ans.add(subAns);}//剪枝if(left < right)return;//左分支if(left < n){
    dfs(ans,subAns + "(",left + 1,right,n);}//右分支if(right < n){
    dfs(ans,subAns + ")",left,right + 1,n);}}public static void main(String[] args) {
    int num = 3;Solution solution = new Solution();List<String> strings = solution.generateParenthesis(num);for (String string : strings) {
    System.out.println(string);}}
}

BFS

显然要借助辅助变量栈，使用数据结构Node存储节点状态
当右括号的剩余数量大于左括号剩余数量时肯定时错误答案，这个分支可以去除

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;/*** 如何使用bfs遍历,借助栈吧*/
public class Solution {
    public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList<>();ArrayDeque<Node> queue = new ArrayDeque<>();queue.addLast(new Node("",n,n));bfs(ans,queue,n,n);return ans;}//当右括号的剩余数量大于左括号剩余数量时肯定时错误答案，这个分支可以去除public void bfs(List<String> ans,ArrayDeque<Node> queue,int left,int right){
    //栈不空就循环while(queue.size() != 0){
    Node temp = queue.pop();//得到答案if(temp.left == 0 && temp.right == 0){
    ans.add(temp.subAns);}//进入左分支，带剪枝if(temp.left > 0 && temp.left - 1 <= temp.right){
    queue.addLast(new Node(temp.subAns + "(",temp.left - 1,temp.right));}//进入右分支，带剪枝if(temp.right > 0 && temp.left <= temp.right - 1){
    queue.addLast(new Node(temp.subAns + ")", temp.left, temp.right - 1));}}}public static void main(String[] args) {
    //ArrayDeque如何运作,pop弹出第一个节点，push在第一个节点前面加节点，addLast在最后加节点int num = 3;Solution solution = new Solution();List<String> strings = solution.generateParenthesis(num);for (String string : strings) {
    System.out.println(string);}}
}class Node{
    String subAns;//当前的字串int left;//左括号剩余int right;//右括号剩余public Node(String subAns, int left, int right) {
    this.subAns = subAns;this.left = left;this.right = right;}
}