1.全排列

• 2.12

  • used 数组需要穿进去

• 11.21

  • 之前的记录怎么没了?
  • 记住公式,res,path,used
  • 总循环下,退出判定为path和nums相等
  • 次循环下,看used是否被用过,(不用判断是不是同一个i了)

class Solution {
    // 存放最终的所有排列
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        // 记录当前的路径
        List<Integer> path = new ArrayList<>();
        // 记录某个数字是否被使用过，默认全是 false
        boolean[] used = new boolean[nums.length];
        backtrack(nums, path, used);
        return res;
    }
    // 递归函数
    public void backtrack(int[] nums, List<Integer> path, boolean[] used) {
        // 1. 结束条件：当路径长度等于数组长度，说明填满了
        if (path.size() == nums.length) {
            // 【重要】这里必须 new 一个新的 ArrayList
            // 如果直接 add(path)，加进去的是引用，后续 path 变化，结果也会全变！
            res.add(new ArrayList<>(path));
            return;
        }
        // 2. 做选择
        for (int i = 0; i < nums.length; i++) {
            // 如果这个数字已经被用过了，跳过
            if (used[i]) {
                continue;
            }
            // --- 做决定 (进) ---
            path.add(nums[i]);  // 把数字加入路径
            used[i] = true;     // 标记为已使用
            // --- 递归下一层 ---
            backtrack(nums, path, used);
            // --- 撤销决定 (退/回溯) ---
            path.remove(path.size() - 1); // 把刚加进去的数字拿出来
            used[i] = false;              // 标记为未使用，方便下次循环或其他分支使用
        }
    }
}