LeetCode 46. 全排列（回溯算法解决）

lscho 发布于2021-10-13 09:40 / 2815人阅读

摘要：截止到目前我已经写了多道算法题，其中部分已经整理成了文档，目前总共有多页并且还会不断的增加，大家可以免费下载下载链接提取码全排列也是一道经典的题，之前在讲，什么叫回溯算法，一看就会，一写就废的时候，也提到过使用回溯算法

截止到目前我已经写了 600多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

全排列也是一道经典的题，之前在讲450，什么叫回溯算法，一看就会，一写就废的时候，也提到过使用回溯算法来解决，具体细节可以看下。假设数组长度是n，我们可以把回溯算法看做是一颗n叉树的前序遍历，第一层有n个子节点，第二层有n-1个子节点……，来看个视频

视频链接

代码如下

public List<List<Integer>> permute(int[] nums) {    List<List<Integer>> list = new ArrayList<>();    backtrack(list, new ArrayList<>(), nums);    return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {    //终止条件，如果数字都被使用完了，说明找到了一个排列，（可以把它看做是n叉树到    //叶子节点了，不能往下走了，所以要返回）    if (tempList.size() == nums.length) {        //因为list是引用传递，这里必须要重新new一个        list.add(new ArrayList<>(tempList));        return;    }    //（可以把它看做是遍历n叉树每个节点的子节点）    for (int i = 0; i < nums.length; i++) {        //因为不能有重复的，所以有重复的就跳过        if (tempList.contains(nums[i]))            continue;        //选择当前值        tempList.add(nums[i]);        //递归（可以把它看做遍历子节点的子节点）        backtrack(list, tempList, nums);    }}

我们就用数组[1,2,3]来测试一下，看一下打印结果

[1, 2, 3]

是不是很意外，示例1给出的是6个结果，这里打印的是1个，这是因为list是引用传递，当遍历到叶子节点以后要往回走，往回走的时候必须把之前添加的值给移除了，否则会越加越多，我们来看下视频
视频链接

再来看下代码

public List<List<Integer>> permute(int[] nums) {    List<List<Integer>> list = new ArrayList<>();    backtrack(list, new ArrayList<>(), nums);    return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {    //终止条件，如果数字都被使用完了，说明找到了一个排列，（可以把它看做是n叉树到    //叶子节点了，不能往下走了，所以要返回）    if (tempList.size() == nums.length) {        //因为list是引用传递，这里必须要重新new一个        list.add(new ArrayList<>(tempList));        return;    }    //（可以把它看做是遍历n叉树每个节点的子节点）    for (int i = 0; i < nums.length; i++) {        //因为不能有重复的，所以有重复的就跳过        if (tempList.contains(nums[i]))            continue;        //选择当前值        tempList.add(nums[i]);        //递归（可以把它看做遍历子节点的子节点）        backtrack(list, tempList, nums);        //撤销选择，把最后一次添加的值给移除        tempList.remove(tempList.size() - 1);    }}

我们来看一下运行结果

[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]

这题使用回溯算法的还一种解决方式就是交换，比如我们先选择第一个数字，然后和后面的所有数字都交换一遍，这样全排列的第一位就确定了。然后第二个数字在和后面的所有数字交换一遍，这样全排列的第二位数字也确定了……，一直继续下去，直到最后一个数字不能交换为止，这里画个图来看一下

来看下代码

public List<List<Integer>> permute(int[] nums) {    List<List<Integer>> res = new ArrayList<>();    backtrack(nums, 0, res);    return res;}public void backtrack(int[] nums, int index, List<List<Integer>> res) {    //到最后一个数字，没法再交换了，直接把数组转化为list    if (index == nums.length - 1) {        //把数组转为list        List<Integer> tempList = new ArrayList<>();        for (int num : nums)            tempList.add(num);        //把list加入到res中        res.add(tempList);        return;    }    for (int i = index; i < nums.length; i++) {        //但前数字nums[index]要和后面所有的数字都要交换一遍（包括        // 他自己）        swap(nums, index, i);        //递归，数组[0,index]默认是已经排列好的，然后从index+1开始        //后面元素的交换        backtrack(nums, index + 1, res);        //还原回来        swap(nums, index, i);    }}//交换两个数字的值private void swap(int[] nums, int i, int j) {    if (i != j) {        nums[i] ^= nums[j];        nums[j] ^= nums[i];        nums[i] ^= nums[j];    }}

递归解决

我们来思考这样一个问题，假如数组[1,2,3]，我们知道了[2,3]的全排列结果，只需要把1放到这些全排列的所有位置，即是数组[1,2,3]的全排列，画个图来看一下

//递归解决public List<List<Integer>> permute(int[] nums) {    return helper(nums, 0);}/** * @param nums * @param index 递归当前数字的下标 * @return */private List<List<Integer>> helper(int[] nums, int index) {    List<List<Integer>> res = new ArrayList<>();    //递归的终止条件，如果到最后一个数组，直接把它放到res中    if (index == nums.length - 1) {        //创建一个临时数组        List<Integer> temp = new ArrayList<>();        //把数字nums[index]加入到临时数组中        temp.add(nums[index]);        res.add(temp);        return res;    }    //计算后面数字的全排列    List<List<Integer>> subList = helper(nums, index + 1);    //集合中每个子集的长度    int count = subList.get(0).size();    //遍历集合subList的子集    for (int i = 0, size = subList.size(); i < size; i++) {        //把当前数字nums[index]添加到子集的每一个位置        for (int j = 0; j <= count; j++) {            List<Integer> temp = new ArrayList<>(subList.get(i));            temp.add(j, nums[index]);            res.add(temp);        }    }    return res;}

服务器托管 idc机房托管回溯法全排列 c语言字符串全排列算法最快的全排列算法迷宫c语言回溯算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/122400.html

leetcode 46 Permutations

摘要：例如有如下的全排列想法这道题是用回溯法的思想解决的。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发深度优先搜索，搜索到某个点的时候，先判断该节点是否包含问题的解，如果包含就继续探索，否则就逐层向根节点回溯。题目详情 Given a collection of distinct numbers, return all possible permutations....

jubincn 2019-08-16 11:09 评论0 收藏0
回溯算法讲解--适用于leetcode绝大多数回溯题目

摘要：什么是回溯算法回溯法是一种系统搜索问题解空间的方法。解空间定义为与数字长度相同。最后，为什么要掌握回溯法因为懂了回溯法之后笔试里的很多题就算不了，起码成功运行到之间是没问题的。什么是回溯算法？回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。而往往所谓的dfs，bfs都是在图或者树这种数据...

saucxs 2019-08-16 15:23 评论0 收藏0
【Leetcode】78. 子集

摘要：题目给定一组不含重复元素的整数数组，返回该数组所有可能的子集幂集。说明解集不能包含重复的子集。示例输入输出题解全排列，部分排列这些问题都是回溯的题目。这个题目每个状态都是解，包括空也是解，所以直接都加进去就好。题目给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: nums = [1,2,3] 输出: [ ...

laznrbfe 2019-08-19 11:15 评论0 收藏0
【Leetcode】78. 子集

摘要：题目给定一组不含重复元素的整数数组，返回该数组所有可能的子集幂集。说明解集不能包含重复的子集。示例输入输出题解全排列，部分排列这些问题都是回溯的题目。这个题目每个状态都是解，包括空也是解，所以直接都加进去就好。题目给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: nums = [1,2,3] 输出: [ ...

miqt 2019-07-30 17:56 评论0 收藏0
字符串的全排列

摘要：问题输入一个字符串按字典序打印出该字符串中字符的所有排列。如此递归处理，从而得到所有字符的全排列。记斐波那契数列的第位这件事为，则有。其中，表示去掉那个开头字符的剩余字符串的全排列。问题输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。地址：https://...

sunny5541 2019-08-23 11:38 评论0 收藏0