LeetCode46-全排列（dfs算法）

题目描述

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

全排列的基本思想是：

把待全排列记录分为两个部分：
（1） 第一个记录
（2） 剩下的所有元素
所有记录的全排列就是所有可能出现在第一个位置的记录与剩下所有元素的全排列。
以[1,2,3]为例，
1,2,3的全排列可以看作是
1,[2,3的全排列]
[2,3]的全排列又可以看作是
2,[3的全排列]—————对应123
3,[2的全排列]—————对应132
2,[1,3的全排列]
[1,3]的全排列又可以看作是
1,[3的全排列]—————对应213
3,[1的全排列]—————对应231
3,[1,2的全排列]
[1,2]的全排列又可以看作是
1,[2的全排列]—————对应312
2,[1的全排列]—————对应321

所以很明显，这就是一个递归的思想：给你部分记录，全排列就是所有可能出现在第一个位置的记录与剩下的元素的全排列，剩下的元素的全排列又是剩下的可能出现在第一个位置的元素与剩下的元素的全排列，依次重复下去….

代码实现：

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

    public List<List<Integer>> permute(int[] nums) {
        // 记录路径
        LinkedList<Integer> track = new LinkedList<>();
        // 路径中的元素会被标记为 true，避免重复使用
        boolean[] used = new boolean[nums.length];
        backtrack(nums, track, used);
        return res;
    }

    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
    // 结束条件：nums 中的元素全都在 track 中出现
    public void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used){
        if(track.size() == nums.length){
            // ⭐由于是传入的引用，因此要拷贝一个新的List放入res中，不能直接add(track)
            res.add(new LinkedList(track));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(used[i] == false){
                // 做选择
                used[i] = true;
                track.add(nums[i]);
                // 进入下一层决策树
                backtrack(nums, track, used);
                // 取消选择
                used[i] = false;
                track.removeLast();
            }
        }
    }
}

dfs基本模型

void dfs(int step){
	判断边界
	尝试每一种可能 for(i=1;i<=n;i++){
		继续下一步 dfs(step+1)
		}
	返回
}

关于dfs可以参考以下博文

DFS入门级（模板）_dfs模型_ღ江晚吟的博客-CSDN博客

DFS(深度优先搜索算法)_深度优先算法_Starzkg的博客-CSDN博客