大厂面试经典算法题-46.全排列

#头条创作挑战赛#

排列问题在高中数学中有学到的。n个不重复的数，全排列共有n！ 个。对于全排列问题，典型的解法就是回溯算法。

对于回溯算法，我们之前讲过，本质上是对一个N叉树的for遍历加递归，这是回溯算法的一个基本的框架，其中的前序和后序遍历就是我们在根据问题具体写的处理逻辑了。

class TreeNode {
 int val;
 TreeNode[] childs;
}

public void traverse(TreeNode node) {
 for (int i = 0; i < node.childs.length; i++) {
 // 前序遍历操作
 traverse(node.childs[i]);
 // 后序遍历操作
 }
}

这里递归的前序遍历一般是在进入某个节点之前做的操作，后序遍历一般就是在离开某个节点之后需要做的事情，这里使用逻辑来描述的话，就是“做出选择”和“撤销选择”，其中这个撤销选择向上回归就是一个典型的回溯算法。

通过以上的理解，我们只要在循环中，递归操作之前，做出选择，然后在递归之后，撤销之前的选择，这样我们就可以所有的不同选择的全部组合。在循环递归的过程中，也是会存在一些异常的逻辑情况，我们可以进行逻辑的判断，来规避掉对异常情况的循环递归，提高程序的执行效率。

public List<List<Integer>> permute(int[] nums) {
        traverse(new ArrayList<>(), nums);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();

    public void traverse(List<Integer> lujing, int[] nums) {
        //满足正确结束的条件,直接结束
        Set<Integer> set = new HashSet<>(lujing);
        if (set.size() == nums.length) {
            result.add(new ArrayList<>(lujing));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (lujing.contains(nums[i])) {
                continue;
            }

            // 前序遍历，做出选择
            lujing.add(nums[i]);
            traverse(lujing, nums);
            // 后序遍历，撤销选择
            lujing.remove(lujing.size()-1);
        }
    }

到这里本文就结束了，这里演示的全排列问题的经典回溯算法的解法，使用的是一个最基本的解法，所以在执行用时和内存消耗上面并不是特别的突出。还有一些更高级的优化，比如“交换元素”,这里我就不演示了。

大家在学习算法的时候，最好不要过早的接触一些高级优化手段，否则有可能会产生自我怀疑，建议先使用这些基础解法，随着刷题越来越熟练，一些更高级的算法和优化这个时候接触就更加合适了。

点赞关注一下哈，后续会继续分享。