00回溯中等 leetcode22. 括号生成

递归是一种算法结构。递归会出现在子程序中，形式上表现为直接或间接的自己调用自己。
回溯是一种算法思想，它是用递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。发现选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。

上面总结引用自“琦小虾”的原创博客：LeetCode 刷题笔记——递归与回溯的理解

分析

回溯思想，在""的后面添加括号直到字符串的长度达到n对合法的括号。每次递归都在右边添加一个左括号或者右括号，然后递归下去。
利用左右括号数量来判断生成的括号是否有效。

import java.util.ArrayList;
class Solution {
    /*
    采用回溯思想，不要生成所有的字符串然后去判断是不是有效的，那样太低效。
    每一步有两种选择，生成左括号，生成右括号，两种选择都要选择，然后判断选择之后是否有效。
    利用左右括号数量来判断深成的括号是否有效。
    当右括号的数量比左括号数量多时肯定无效，即剩余的右括号不能多于左括号。
    当左(右)括号的数量超过了n肯定无效。 
    当左右括号都为零，说明之前左括号一直大于等于右括号的数量，左右括号都为零说明生成了同等数量的括号，生成的字符串肯定有效，因为无效的都被排除了。	
    */
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        process(n,n,"",list);
        return list;
    }

    public void process(int left,int right,String str,List<String> list){
        if(right < left){//此判断是“剪枝”，排除了无效的情况。
            return ;
        }
        if(left == 0 && right == 0){
            list.add(str);
            return ;
        }
        if(left > 0){
            process(left-1,right,str+"(",list);
        }
        if(right > 0){
            process(left,right-1,str+")",list);
        }
    }
}