回溯中等1 种解法

#46全排列

对不含重复值的数组，生成元素的全部排列。

#回溯#数组#排列

解题主线

排列的每一层都要从数组开头扫描，used 按下标标记当前路径已经使用的元素。

当路径长度等于数组长度时得到一个叶子结果，必须复制路径再保存。

解法 1：使用标记回溯

每层遍历所有下标，跳过当前路径中已经使用的元素，直到路径包含全部元素。

时间复杂度

O(n × n!)，共有 n! 个排列且每次复制长度 n

空间复杂度

O(n)，不计输出

46. 全排列 · 使用标记回溯

java

import java.util.ArrayList;
import java.util.List;

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

    private void backtrack(int[] nums, boolean[] used,
                           List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.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, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

每层遍历所有下标，跳过当前路径中已经使用的元素，直到路径包含全部元素。

两个旧文件的核心递归完全相同，合并后消除了实例字段状态。

边界与易错点

不能像组合题一样传 start，否则会漏掉后续位置选择较小下标元素的排列。
递归返回后要同时移除路径末项并清除对应 used 标记。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q046_permute.javabacktrack/Q046_permute_traverse.java