LeetCode 46. 全排列（回溯）

文章目录

• 前言
• 题目
• 题解
• NO1：回溯
• 参考资料

前言

当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：46. 全排列，难度：中等。

题目描述(摘自leetcode)：

给定一个不含重复数字的数组 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 中的所有整数 互不相同

本地调试代码：

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        ...
    }

    public static void main(String[] args) {
        final List<List<Integer>> permute = new Solution().permute(new int[]{1, 2, 3});
        System.out.println(permute);
    }

}

---

题解

NO1：回溯

思路：根据题意画出对应回溯情况的二叉树，确定边界条件（出口）以及一些必要的辅助数组、集合等即可。

所需要的一些必要条件如(对应该题)：出口（深度都为3），收集全排序的集合(res)，深搜+回溯产生出来的过程结果集（path），还有最核心的一个问题就是在进行深搜过程中如何排除掉已添加到path的某个结果值？可使用一个与nums数组同大小的状态数组来进行记录，在深搜过程中枚举判断即可！

• 根据图来推出所需要的情况及条件，那么我们就可以来编写递归的函数方法了，对应参数也就是上面举出的。

代码：

public List<List<Integer>> permute(int[] nums) {
    //全排列结果集、一组结果集、标记访问数组（默认为false）
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visitArr = new boolean[nums.length];
    recall(nums,path,0,visitArr,res);
    return res;
}

/**
     * 回溯求得全排列
     * @param nums 待全排列数据集集合
     * @param path 待添加入的一组数据
     * @param depth 深度
     * @param visitArr 标记是否访问数组
     * @param res 全排列结果集
     */
private void recall(int[] nums, List<Integer> path, int depth, boolean[] visitArr,
                    List<List<Integer>> res) {
    //出口条件，到达指定的深度结束
    if (depth == nums.length){
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        //若是没有访问过的情况
        if (!visitArr[i]){
            path.add(nums[i]);
            visitArr[i] = true;
            recall(nums,path,depth + 1,visitArr,res);
            //回溯
            path.remove(path.size() - 1);
            visitArr[i] = false;
        }
    }

}

---

参考资料

[1]. 回溯算法入门级详解 + 练习（持续更新）：讲的较详细推荐

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.12.20