全排列 - LeetCode 热题 55

2024-05-08 00:52

文章标签 leetcode 热题排列

本文主要是介绍全排列 - LeetCode 热题 55，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家好！我是曾续缘😆

今天是《LeetCode 热题 100》系列

发车第 55 天

回溯第 1 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

全排列
给定一个不含重复数字的数组 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 中的所有整数 互不相同
难度：💖💖

解题方法

这道题要求给定一个不含重复数字的数组，返回其所有可能的全排列。我们可以使用回溯算法来解决这个问题。

首先，我们将输入的数组 nums 转换为一个 ArrayList list_nums，方便进行元素交换操作。

接下来是 backtrack 方法，它采用递归的方式来生成全排列。在 backtrack 方法中，我们有两个参数，一个是当前的列表 nums，另一个是当前处理的位置 cur。

首先，我们检查如果 cur 已经到达了列表的末尾，就将当前列表加入到最终结果 ans 中。

然后，我们从当前位置开始，枚举当前位置可以填入的值，也就是依次将当前位置的元素与后面的元素进行交换，然后递归调用 backtrack 方法，处理下一个位置。

当递归调用完成后，说明我们已经将当前交换过的值的所有后续情况处理完了，我们需要将元素交换回来，使得列表回到交换前的状态，以确保下一次迭代时列表的顺序是正确的。

这样通过不断地交换元素和递归调用，直到遍历完整个数组，就能够得到所有可能的全排列。

Code

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> list_nums = new ArrayList<Integer>();for(int x : nums){list_nums.add(x);}backtrack(list_nums, 0, ans);return ans;}private void backtrack(List<Integer> nums, int cur, List<List<Integer>> ans){if(cur == nums.size()){ans.add(new ArrayList<Integer>(nums));}for(int i = cur; i < nums.size(); i++){Collections.swap(nums, cur, i);backtrack(nums, cur + 1, ans);Collections.swap(nums, cur, i);}}
}