leetcode_46.全排列

2024-05-04 15:08
19人已看

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

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整数 互不相同

代码思路：

backTracking 方法是核心递归函数，它通过深度优先搜索来生成所有可能的排列组合。该方法接受两个参数：nums 数组和一个表示哪些数字已经被使用的布尔数组 used。
在 backTracking 方法中，首先检查 temp 列表的大小是否达到了 nums 数组的长度。如果是，说明当前排列已经包含了所有的数字，将该排列添加到结果列表 ans 中，并返回。
如果 temp 列表的大小没有达到 nums 数组的长度，则遍历 nums 数组的每个元素。如果当前元素已经被使用过（即 used[i] 为真），则跳过当前循环。
如果当前元素没有被使用过，则将其添加到 temp 列表中，标记为已使用，并递归调用 backTracking 方法。递归返回后，需要将当前添加的元素从 temp 列表中移除，并标记为未使用，以便进行下一次循环时重新使用。
通过这种深度优先搜索的方式，不断尝试所有可能的排列组合，直到所有数字都被使用过，生成了所有的排列组合。

class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backTracking(nums, used);
        return ans;
    }

    public void backTracking(int[] nums,  boolean[] used) {
        if (temp.size() >= nums.length) {
            ans.add(new LinkedList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            temp.add(nums[i]);
            used[i] = true;
            backTracking(nums, used);
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
}