括号生成（重点！！！）

这一题就是组合问题，可选集只有两个，但是这一题既不是index也不是used的：

注意到了吗，他的剪枝不是单纯地index那种：用了左括号后面就一定不能用了
也不是used，往下的时候不能用左括号，回上来可以继续用

而是一颗完全的树，因此最暴力的做法显然是直接遍历整颗树，但是这样显然不行
如何剪枝呢？
关键在这里：放置右括号有且仅有当前左括号数量大于0
因此就知道了我们的第一个大剪枝

但是存在另一个更复杂的难点：
我们不是像其他回溯题一样，一个for下一个dfs就可以搞定的（除了暴力做法），因为在考虑剪枝的情况下，我们两次左右问题的dfs是不同的，因为如果使用for的话，我们直接pop出来应该进入兄弟问题，但是这里会出现：
左右括号计数不同，不能写同一个dfs的递归
比如：

let us = ('(', ')');
for x in 0..2 {
    temp.push(us.x);
    dfs(res, temp, ?, ?);
    temp.pop();
}

那么就算在for里也需要根据情况拆为两个dfs，除非能使用不用计数的方法
所以具体来说就是，对于这种情况，我们在分析左右子问题的时候：
关键是，在什么时候进入子问题，即寻找满足进入子问题的条件才进入！！
这样写出来的for才是完备的

/// 22. 括号生成
pub fn generate_parenthesis(n: i32) -> Vec<String> {
    fn dfs(res: &mut Vec<String>, temp: &mut String, l_num: usize, r_num:usize) {
        if l_num == r_num && l_num == 0{
            res.push(temp.clone());return;
        }
        // 如果左括号大于了总括号数，或者右括号多了，直接剪枝
        // 使用减法策略的话，不需要判定左括号过多
        if r_num < l_num{
            return;
        }
        // 左问题,注意模拟在for内的阶之间的遍历的时候，这一题特点在于
        // 两边不是都可以放进去讨论的，即不是for下同一套东西就行
        // 而且也不是used也不是index
        if l_num > 0 {
            temp.push('(');
            dfs(res, temp, l_num - 1, r_num);
            temp.pop();
        }
        // 右问题
        if r_num > 0 {
            temp.push(')');
            dfs(res, temp, l_num, r_num - 1);
            temp.pop();
        }
    }
    let mut res = Vec::new();
    let mut temp = String::new();
    // 使用减法
    dfs(&mut res, &mut temp, n as usize, n as usize);
    res
}

N皇后

与括号生成比较

参考水印处的题解，可以注意到，n皇后问题采用回溯的做法，与常规的回溯问题的框架上没什么区别，也是树状后序遍历，不同点在于，剪枝方式不同

就像括号生成一样，N皇后问题也是既不是index也不是used的，但是比括号生成更为简单一点，因为for下面有一个同样的评判标准，而不是括号生成那样有着两套dfs。

第一个问题，矩阵斜线特性

N皇后问题的难点也是在于这个评判标准：如何查找斜线上存在皇后？
答案在下面两个规律上：


因此我们可以使用hashSet来进行判断，比如对于合为5的斜线情况，我们只需要看set中是否存在5即可，如果存在就说明已经放入了

第二个问题，如何存每一次的棋盘并转换

可以注意到，存在一个问题是，我们的结果是Vec<Vec<String>>，那么每一次就应该放入Vec<String>，该数组描述了整个棋盘，也即有四项
但是问题在于，我们不能如同之前一样简单地放入：

temp.push()
dfs()
temp.pop()

因为，在每一项放入的位置在每一行必然是不一样的，如果在这里进行区分就很复杂
解决方法就是使用一个listVec<i32>，存储的信息为第i行第j列有皇后可以描述为temp[i] = j，注意到了吗，这是一个hash表的思路

代码

/// n皇后
pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
    fn dfs(n: i32, col: &mut HashSet<i32>, dia1: &mut HashSet<i32>, dia2: &mut HashSet<i32>,
           res: &mut Vec<Vec<String>>, temp: &mut Vec<i32>, depth: i32) {
        if depth >= n {
            res.push(construct(temp));
            return;
        }
        // 深度depth代表了行，for是同层的，代表了列
        // 这里不能用index的原因就是，每一列都需要被考虑是否可以放
        for x in 0..n {
            if col.contains(&x) {
                continue;
            }
            let dia = depth + x;
            if dia1.contains(&dia) {
                continue;
            }
            let dia = depth - x;
            if dia2.contains(&dia) {
                continue;
            }

            // 下一个问题就是，如何存储临时的变量
            temp[depth as usize] = x;
            col.insert(x);
            dia1.insert(depth + x);
            dia2.insert(depth - x);
            dfs(n, col, dia1, dia2, res, temp, depth + 1);
            temp[depth as usize] = -1;
            col.remove(&x);
            dia1.remove(&(depth + x));
            dia2.remove(&(depth - x));
        }
    }
    fn construct(temp: &mut Vec<i32>) -> Vec<String> {
        let mut res = Vec::new();
        for x in 0..temp.len() {
            let x = temp[x] as usize;
            let mut ss = ".".repeat(temp.len()).to_string();
            // 注意这个方法
            ss.replace_range(x..x+1, "Q");
            res.push(ss);
        }
        res
    }

    let mut res = Vec::new();
    let mut col = HashSet::new();
    let mut dia1 = HashSet::new();
    let mut dia2 = HashSet::new();
    let mut temp = vec![-1; n as usize];
    dfs(n, &mut col, &mut dia1, &mut dia2, &mut res, &mut temp, 0);
    res
}