大家好！我是曾续缘😆

今天是《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);
        }
    }
}