【算法题】全排列

题目

思路

看到 返回其所有可能的全排列，那我们第一时间就想到了穷举。想到了穷举，那第一时想到的算法是什么？

没错，是回溯算法。

回溯算法的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

此题中，以123为例，我们把全排列的位置作为探索点向前探索，如下：

什么时候探索结束呢？当排列的个数等于给出的数组个数时结束探索。

结束探索后，我们把符合条件的排列存入集合，然后向后回溯，再次排列，直到所有的路径探索完成为止。

回溯算法的难点在于，回溯算法一般是利用递归算法来实现的，而且递归中带有循环，这更加难以理解。

面对递归我们不能代入值去一层一层的验证，而是要理解其中一步的逻辑。具体可以看之前的文章：

回溯算法是有模版的，模版如下：

示例代码

示例代码如下（每道算法题的解法都可以不一样，欢迎大家提出运行速度更快，空间占用更少的解法）：

public class Test3 {
    //定义全局变量
    List<List<Integer>> resultList = new ArrayList<>();
    List<Integer> nodeList = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        //定义标记数组,默认赋值为false
        // 因为一个数字只能使用一次因此需要对数组内的每个数字进行标记
        boolean[] flag = new boolean[nums.length];
        for(int i = 0;i<nums.length;i++){
            flag[i] = false;
        }
        //通过递归找到一条结果链上的所有节点
        findNodeList(nums,flag);
        return resultList;
    }

    public void findNodeList(int[]nums,boolean[] flag){
        //定义结束条件
        if(nodeList.size() == nums.length){
            //结果保存
            resultList.add(new ArrayList(nodeList));
            return;
        }
        //设置当前节点的值,需要使用回溯算法
        //当前节点可以是数组内的任何一个值
        //因此从数组的第一位开始循环
        for(int i = 0;i<nums.length;i++){
            //没有使用过才能使用
            if(flag[i] == false){
                //设置当前节点
                nodeList.add(nums[i]);
                flag[i] = true;
                //设置下一个节点
                findNodeList(nums,flag);
                //回溯，此处要结合递归理解
                //当达成结束条件后，向后回溯一个节点，因此之前的操作都得反向来一遍
                //删除刚刚加入的节点
                nodeList.remove(nodeList.size() - 1);
                //设置为未使用
                flag[i] = false;
            }
        }
    }
}