51. N-Queens

 一刷 07/2022

Version #1 Backtracking

Time O(N!)

Space O(N)

Runtime: 8 ms, faster than 46.32% of Java online submissions for N-Queens.

Memory Usage: 47 MB, less than 14.31% of Java online submissions for N-Queens.

class Solution {

    public List<List<String>> solveNQueens(int n) {

        List<List<String>> result = new ArrayList<>();

        char[] array = new char[n];

        Arrays.fill(array, '.');

        helper(n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>(), new ArrayList<>(), result, array);

        return result;

    }

    

    private void helper(int n, int y, Set<Integer> cols, Set<Integer> diff, Set<Integer> sum, List<String> path, List<List<String>> result, char[] array) {

        if (y == n) {

            result.add(new ArrayList<>(path));

            return;

        }

        for (int x = 0; x < n; x++) {

            if (cols.contains(x) || diff.contains(y - x) || sum.contains(y + x)) {

                continue;

            }

            array[x] = 'Q';

            cols.add(x);

            diff.add(y - x);

            sum.add(y + x);

            path.add(new String(array));

            array[x] = '.';

            helper(n, y + 1, cols, diff, sum, path, result, array);

            cols.remove(x);

            diff.remove(y - x);

            sum.remove(y + x);

            path.remove(path.size() - 1);

        }

    }

}