#头条创作挑战赛#

排列问题在高中数学中有学到的。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);        }    }

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

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

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