46. 全排列#

class Solution {
    // 主函数：返回 nums 的所有全排列
    public List<List<Integer>> permute(int[] nums) {
        // res：用于保存最终所有排列结果
        List<List<Integer>> res = new ArrayList<>();
        // 启动回溯：
        // - used 用于标记每个下标对应的数字是否已被当前路径使用
        // - path 记录当前正在构建的排列
        // - res 收集完整排列
        backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
        // 返回所有收集到的排列
        return res;
    }

    // 回溯函数：在当前 path 基础上继续尝试未使用的数字
    private void backtrack(int[] nums, boolean[] used, 
                          List<Integer> path, List<List<Integer>> res) {
        // 终止条件：当路径长度等于数组长度时，说明形成了一个完整排列
        if (path.size() == nums.length) {
            // 注意要拷贝一份 path 再加入结果，避免后续回溯修改影响已保存结果
            res.add(new ArrayList<>(path));
            // 当前分支完成，返回上一层继续尝试其他选择
            return;
        }

        // 枚举每一个数字下标，尝试把还没用过的数字放到当前位置
        for (int i = 0; i < nums.length; i++) {
            // 剪枝：如果 nums[i] 已在当前路径中使用，则跳过
            if (used[i]) continue;

            // 做选择：把 nums[i] 放入当前路径，并标记为已使用
            used[i] = true;
            path.add(nums[i]);

            // 递归进入下一层：继续填下一个位置
            backtrack(nums, used, path, res);

            // 撤销选择（回溯）：
            // 1) 删除路径最后一个数字
            // 2) 恢复 used 状态，便于后续分支复用该数字
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}