LeetCode 52. N 皇后 II java题解

https://leetcode.cn/problems/n-queens-ii/description/

N皇后问题中，求的是每一种解法，而在2中要求解法的个数，可以直接沿用1的代码，返回一个整数代表种类数。

class Solution {boolean[] a;boolean[] b;boolean[] c;int count=0;public int totalNQueens(int n) {a=new boolean[n];b=new boolean[2*n];c=new boolean[2*n];ArrayList<Integer> tmp=new ArrayList<>();//记录每一行，放在哪一列find(0,n,tmp);//第几个（放在第几行）； 一共n个return count;}public void find(int i,int n,ArrayList<Integer> tmp){if(i==n){//前面已经全部找到了，加入结果count++;return;}for(int j=0;j<n;j++){//遍历每一列if(a[j]||b[i-j+n]||c[i+j]){continue;//跳过已用的}//标记用过a[j]=true;b[i-j+n]=true;c[i+j]=true;tmp.add(j);//代表放在第j列了find(i+1,n,tmp);//回溯a[j]=false;b[i-j+n]=false;c[i+j]=false;tmp.remove(tmp.size()-1);//代表放在第j列了}}    
}
/**
记录是否用过：
这一行是否用过。每一行放一个，所以不必记录行。
这一列是否用过
这一（左上到右下）对角线方向是否用过： i-j相同。可能存在负数所以加n.
这一（右上到左下）对角线方向是否用过：i+j是否相同。和不超过2n*/