46 全排列

一、题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

二、题解

思路：你可以把这个问题想象成在多个空位上填数字。对于 nums = [1, 2, 3]：

  1. 第一个位置有 3 种选择（1、2 或 3）。
  2. 假设第一个位置选了 1，那么第二个位置就只剩下 2 种选择（2 或 3）。
  3. 假设第二个位置选了 2，第三个位置就只有 1 种选择（3）。
  4. 当所有位置都填满时，我们就得到了一个完整的排列 [1, 2, 3]。然后我们“撤销”最后一步（回溯），去尝试其他的可能性。

回溯算法的三要素：

  1. 路径 (path)：记录当前已经做出的选择（例如当前已经选了 [1, 2]）。
  2. 选择列表：当前还可以做出的选择。为了快速知道某个数字是否已经被选过，我们可以用一个布尔数组 used 来标记。
  3. 结束条件：当“路径”的长度等于 nums 的长度时，说明我们找到了一个完整的全排列，将其加入结果集中。
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 用于存放所有结果的集合
        List<List<Integer>> res = new ArrayList<>();
        // 用于存放当前的一条路径
        List<Integer> path = new ArrayList<>();
        // 标记数组，用来判断某个元素是否已经被使用过
        boolean[] used = new boolean[nums.length];

        // 开始回溯
        backtrack(nums, path, used, res);
        return res;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        // 触发结束条件：如果当前路径的长度等于数组长度，说明找到了一个全排列
        if (path.size() == nums.length) {
            // 注意：必须 new 一个新的 ArrayList，否则后续的回溯会修改这个 path
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历所有可能的选择
        for (int i = 0; i < nums.length; i++) {
            // 如果这个数字已经被用过了，跳过
            if (used[i]) {
                continue;
            }

            // 做选择
            path.add(nums[i]);
            used[i] = true;

            // 递归进入下一层
            backtrack(nums, path, used, res);

            // 撤销选择（回溯过程的核心）
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

时间复杂度：O(N×N!)O(N \times N!)

空间复杂度：O(N)O(N)

评论