算法题每日一练:全排列
一、问题描述
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
题目链接:全排列
二、题目要求
样例 1
复制代码
样例 2
复制代码
考察
复制代码
三、问题分析
本题是开启回溯算法刷题的第4
题,之前没有了解过可以看一下这篇题解,讲解比较详细。
这一题和之前刷的组合题目回溯类型
是不一样的,组合是不要求顺序,比如[1,2,3]和[2,1,3]是相同的,而对于排列来说确实不同的。所以高中学的排列组合,排列讲究顺序、组合讲究元素。
下面我们来讲解一下排列:
第一式:函数初始
我们要初始化一个函数来承载回溯,函数里面的参数如何确定呢?
首先,要传入给定的数组信息,目标值,初始遍历的下标。
复制代码
第二式:终止条件
什么时候结束继续向下开始搜索的条件呢?
题目要求全排列,那当我们数组里面的元素等于 nums.size()不就行了?
复制代码
第三式:剪枝优化
这一题不需要剪枝操作。
第四式:递归处理
复制代码
如上面的树形结构,这一题遍历我们需要从头开始遍历,循环的 i 不受数组元素初始下标的影响。
由于数组内的元素只能使用一次,我们要判断这个元素是否被使用过,用 visit[i]记录(为 0 没有使用,为 1 使用过)。
运算过程如下所示:
复制代码
模板:
复制代码
冲冲冲!
四、编码实现
复制代码
五、测试结果
版权声明: 本文为 InfoQ 作者【知心宝贝】的原创文章。
原文链接:【http://xie.infoq.cn/article/cccfe3747dcd4d936ea00ea71】。文章转载请联系作者。
评论