回溯模板：排列、组合、子集问题的通用框架#

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 收集所有合法解，每个解是一条路径副本
    List<Integer> path = new ArrayList<>(); // 当前递归路径（决策树从根到当前节点）

    public List<List<Integer>> solve(int[] nums) {
        backtrack(nums, 0); // 从第 0 层（起点）开始搜索
        return result; // 返回所有搜索得到的解
    }

    private void backtrack(int[] nums, int startIndex) {
        if (isEnd(nums, startIndex)) { // 到达终止条件：根据题型可能是选满、走完、凑够目标等
            result.add(new ArrayList<>(path)); // 注意拷贝 path，避免后续回溯污染已存答案
            return; // 当前分支结束
        }

        for (int index = startIndex; index < nums.length; index++) { // 枚举当前层候选元素
            if (!isValid(nums, index, startIndex)) { // 剪枝：不合法分支直接跳过
                continue;
            }

            path.add(nums[index]); // 做选择：把当前元素加入路径
            backtrack(nums, index + nextStep(nums, index)); // 进入下一层（不同题型步长不同）
            path.remove(path.size() - 1); // 撤销选择：恢复路径到进入本层前
        }
    }

    private boolean isEnd(int[] nums, int startIndex) {
        return false; // 模板占位：判断是否达到收集答案的时机
    }

    private boolean isValid(int[] nums, int index, int startIndex) {
        return true; // 模板占位：判断当前选择是否合法（去重、越界、约束校验等）
    }

    private int nextStep(int[] nums, int index) {
        return 0; // 模板占位：下一层起点偏移（子集/组合常为 1，其他题型可自定义）
    }
}

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 保存所有子集
    List<Integer> path = new ArrayList<>(); // 当前子集内容

    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0); // 从下标 0 开始尝试“选/不选”
        return result;
    }

    private void backtrack(int[] nums, int startIndex) {
        result.add(new ArrayList<>(path)); // 子集题：每到一层，当前 path 都是一个合法子集

        for (int index = startIndex; index < nums.length; index++) { // 仅向后选择，避免重复
            path.add(nums[index]); // 选择 nums[index]
            backtrack(nums, index + 1); // 下一层从 index+1 开始
            path.remove(path.size() - 1); // 回退，尝试下一个元素
        }
    }
}

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 保存所有满足目标和的组合
    List<Integer> path = new ArrayList<>(); // 当前组合路径

    public List<List<Integer>> combine(int[] nums, int target) {
        backtrack(nums, target, 0, 0); // 参数：数组、目标和、起点、当前和
        return result;
    }

    private void backtrack(int[] nums, int target, int startIndex, int sum) {
        if (sum == target) { // 命中目标，当前路径是一组可行解
            result.add(new ArrayList<>(path)); // 复制保存
            return; // 停止向下扩展（再加只会更大）
        }

        if (sum > target) { // 超过目标，剪枝
            return;
        }

        for (int index = startIndex; index < nums.length; index++) { // 从 startIndex 起选，保证组合不重复
            path.add(nums[index]); // 选择当前数字
            backtrack(nums, target, index + 1, sum + nums[index]); // 进入下一层并累加和
            path.remove(path.size() - 1); // 回退
        }
    }
}

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 保存所有排列
    List<Integer> path = new ArrayList<>(); // 当前排列路径
    boolean[] used; // used[i] = true 表示 nums[i] 已在当前路径中使用

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length]; // 初始化全部未使用
        backtrack(nums); // 从空路径开始构造排列
        return result;
    }

    private void backtrack(int[] nums) {
        if (path.size() == nums.length) { // 路径长度等于数组长度，得到一个完整排列
            result.add(new ArrayList<>(path)); // 收集答案
            return;
        }

        for (int index = 0; index < nums.length; index++) { // 排列题每层都从 0 开始尝试
            if (used[index]) { // 已使用元素不能重复放入当前排列
                continue;
            }

            used[index] = true; // 标记使用
            path.add(nums[index]); // 入路径
            backtrack(nums); // 递归构造下一位
            path.remove(path.size() - 1); // 回退路径
            used[index] = false; // 撤销使用标记
        }
    }
}

class Solution {
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四连通方向：下、上、右、左

    private boolean dfs(char[][] board, int row, int col, String word, int index) {
        if (index == word.length()) { // 所有字符都已匹配成功
            return true;
        }

        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) { // 边界检查
            return false;
        }

        if (board[row][col] != word.charAt(index)) { // 当前格字符不匹配，剪枝
            return false;
        }

        char original = board[row][col]; // 保存原字符，便于回溯恢复
        board[row][col] = '#'; // 做访问标记，防止同一路径重复使用该格

        for (int[] direction : directions) { // 枚举四个方向继续匹配下一个字符
            int nextRow = row + direction[0]; // 下一行坐标
            int nextCol = col + direction[1]; // 下一列坐标
            if (dfs(board, nextRow, nextCol, word, index + 1)) { // 只要任一方向成功即可提前返回
                board[row][col] = original; // 返回前恢复现场
                return true;
            }
        }

        board[row][col] = original; // 所有方向失败，恢复现场供其他路径使用
        return false; // 当前起点/路径无法继续匹配
    }
}