algorithms5Backtracking

1package pkg4algorithms;2 3/*4 * algorithms5Backtracking.java5 * -----------------6 * Build candidates incrementally and abandon ("backtrack") a path as soon as it7 * cannot lead to a valid solution. Template: choose -> explore -> un-choose.8 *9 * Covered: subsets (power set), permutations, combinations, and N-Queens count.10 */11import java.util.*;12 13public class algorithms5Backtracking {14 15    static List<List<Integer>> subsets(int[] nums) {16        List<List<Integer>> res = new ArrayList<>();17        backtrackSubsets(nums, 0, new ArrayList<>(), res);18        return res;19    }20    static void backtrackSubsets(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {21        res.add(new ArrayList<>(path));               // every prefix is a subset22        for (int i = start; i < nums.length; i++) {23            path.add(nums[i]);                        // choose24            backtrackSubsets(nums, i + 1, path, res); // explore25            path.remove(path.size() - 1);             // un-choose26        }27    }28 29    static List<List<Integer>> permutations(int[] nums) {30        List<List<Integer>> res = new ArrayList<>();31        backtrackPerm(nums, new boolean[nums.length], new ArrayList<>(), res);32        return res;33    }34    static void backtrackPerm(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {35        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }36        for (int i = 0; i < nums.length; i++) {37            if (used[i]) continue;38            used[i] = true; path.add(nums[i]);39            backtrackPerm(nums, used, path, res);40            used[i] = false; path.remove(path.size() - 1);41        }42    }43 44    static List<List<Integer>> combinations(int n, int k) {45        List<List<Integer>> res = new ArrayList<>();46        backtrackComb(1, n, k, new ArrayList<>(), res);47        return res;48    }49    static void backtrackComb(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {50        if (path.size() == k) { res.add(new ArrayList<>(path)); return; }51        for (int i = start; i <= n; i++) {52            path.add(i);53            backtrackComb(i + 1, n, k, path, res);54            path.remove(path.size() - 1);55        }56    }57 58    // N-Queens: count distinct ways to place n non-attacking queens.59    static int nQueens(int n) {60        return placeQueen(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]);61    }62    static int placeQueen(int row, int n, boolean[] cols, boolean[] diag, boolean[] anti) {63        if (row == n) return 1;64        int count = 0;65        for (int col = 0; col < n; col++) {66            int d = row - col + n, a = row + col;67            if (cols[col] || diag[d] || anti[a]) continue;       // pruning68            cols[col] = diag[d] = anti[a] = true;69            count += placeQueen(row + 1, n, cols, diag, anti);70            cols[col] = diag[d] = anti[a] = false;71        }72        return count;73    }74 75    public static void main(String[] args) {76        System.out.println("subsets([1,2,3]) = " + subsets(new int[]{1, 2, 3}));77        System.out.println("permutations([1,2,3]) = " + permutations(new int[]{1, 2, 3}));78        System.out.println("combinations(4,2) = " + combinations(4, 2));79        System.out.println("N-Queens solutions for n=8: " + nQueens(8));   // expected 9280    }81}