目录

• 1.题目
• 2.自我思路及实现
• 3.总结思路及实现
• 4.相关知识

1.题目

46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

2.自我思路及实现

3.总结思路及实现

回溯法 ：采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现

回溯算法是深度优先遍历思想的用途，用一个不断变化的变量，在尝试各种可能的过程中，搜索需要的结果，用于搜索一个问题的所有解
深度优先遍历强调遍历

全排列问题的树形图

• 每个节点代表求解的不同阶段，这些阶段通过变量的不同的值体现，变量的不同的值称为状态
• 使用深度遍历有回头的过程，在回头之后，需要将状态变量重置回上一个节点，这个操作称为状态重置

状态变量的设置

• 明确这是一个递归的结构，那么递归终止条件就是：一个排列中的数字已经填满，因为每向下一层就会填入一个数字，那么需要一个变量表示递归到第几层
• 由于数组中的数字不能重复使用，那么需要一个布尔数组，初始化为false，每次选择数字后，将布尔数组中代表这个数字的位置设置为true，代表已使用过，这样在选择下一个数字时可以知道该数字是否被使用

时间：共有Ann（排列数）个结果，即n!个结果，每个结果拷贝需要n , 叶子节点的时间复杂度为O(NN!)
非叶子节点个数<2n!，每个节点最多n次循环，时间复杂度为O(NN!)
空间：栈深度为logn

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        if(nums == null || nums.length == 0)
            return res;

        boolean[] visited = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();

        dfs(res, list, visited, nums.length, 0, nums);

        return res;

    }
    void dfs(List<List<Integer>> res, List<Integer> list, boolean[] visited, 
                int length, int depth, int[] nums)
    {
        if(depth == length)
        {
            res.add(new ArrayList<>(list));//拷贝一个新的动态数组
            return;
        }

        for(int i = 0; i < length; i++)
        {
            if(!visited[i])
            {
                list.add(nums[i]);
                visited[i] = true;

                dfs(res, list, visited, length, depth + 1, nums);

                list.remove(list.size() - 1);
                visited[i] = false;

            }
        }
    } 
}

4.相关知识

• 搜索一个问题的所有解——回溯法