N-Queens -- LeetCode

这道题跟N-Queens算法是完全一样的，只是把输出从原来的结果集变为返回结果数量而已。思路我们就不在赘述了，大家可以参见N-Queens，算法的时间复杂度仍然是指数量级的，空间复杂度是O(n)。代码如下：

public int totalNQueens(int n) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    res.add(0);
    helper(n,0,new int[n],res);
    return res.get(0);
}
private void helper(int n, int row, int[] columnForRow, ArrayList<Integer> res)
{
    if(row==n)
    {
        res.set(0,res.get(0)+1);
        return;
    }
    for(int i=0;i<n;i++)
    {
        columnForRow[row]=i;
        if(check(row,columnForRow))
        {
            helper(n,row+1,columnForRow,res);
        }
    }
}
private boolean check(int row, int[] columnForRow)
{
    for(int i=0;i<row;i++)
    {
        if(columnForRow[i]==columnForRow[row] || Math.abs(columnForRow[row]-columnForRow[i])==row-i)
            return false;
    }
    return true;
}