leetcode: N-Queens II

问题描述：

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

 

原问题链接：https://leetcode.com/problems/n-queens-ii/

 

问题分析

　　这个问题和前面的问题基本上一样，无非是不需要保存它的所有位置信息，只需要记录它有多少个布局而已。所以只需要做一点小的改变。在递归函数里定义一个List，每次结束的时候在List里加一个元素。这样到执行结束的时候返回List的长度就可以了。

 

public class Solution {
    public int totalNQueens(int n) {
        int[] list = new int[n];
        List<Integer> result = new ArrayList<Integer>();
        search(0, list, result);
        return result.size();
    }
    
    public void search(int index, int[] list, List<Integer> result) {
        if(index == list.length) {
            result.add(1);
            return;
        }
        for(int i = 0; i < list.length; i++) {
            list[index] = i;
            if(match(list, index))
                search(index + 1, list, result);
        }
    }
    
    boolean match(int[] a, int i) {
        for(int j = 0; j < i; j++) {
            if(a[j] == a[i] || Math.abs(a[j] - a[i]) == Math.abs(j - i))
                return false;
        }
        
        return true;
    }
}