回溯算法：暴力搜索的艺术

void backtrack(List<Integer> path, List<List<Integer>> result, /* 其他参数 */) {
    // 1. 结束条件：收集结果
    if (/* 满足条件 */) {
        result.add(new ArrayList<>(path));   // 注意拷贝！
        return;
    }
    // 2. 遍历选择列表
    for (int choice : choices) {
        if (!isValid(choice)) continue;      // 剪枝
        path.add(choice);                    // 做选择
        backtrack(path, result, /* 更新参数 */);  // 递归
        path.remove(path.size() - 1);        // 撤销选择（回溯）
    }
}

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, boolean[] used,
                       List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int start,
                       List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));          // 每个节点都是合法子集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);   // i+1 避免重复
        path.remove(path.size() - 1);
    }
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int remain, int start,
                       List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if (nums[i] > remain) break;         // 排序后剪枝
        path.add(nums[i]);
        backtrack(nums, remain - nums[i], i, path, res);  // i 不是 i+1，可重复选
        path.remove(path.size() - 1);
    }
}

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(board, 0, res);
    return res;
}

private void backtrack(char[][] board, int row, List<List<String>> res) {
    if (row == board.length) {
        res.add(toList(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (!isValid(board, row, col)) continue;
        board[row][col] = 'Q';
        backtrack(board, row + 1, res);
        board[row][col] = '.';
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
        if (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') return false;
        if (col + (row - i) < n && board[i][col + (row - i)] == 'Q') return false;
    }
    return true;
}

Arrays.sort(nums);   // 必须先排序
// 在 for 循环中：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;