IOS 算法(中级篇) ----- 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
例子
输入： nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入：nums = [0,1]
输出：[[0,1],[1,0]]
输入：nums = [1]
输出：[[1]]
1.回溯法
题意不难理解, 以[1, 2, 3]举例, 最终结果[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
我们可以这样拆分
- [1] + [2, 3] → [1] + [2] + [3] =
[1, 2, 3] - [1] + [3, 2] → [1] + [3] + [2] =
[1, 3, 2] - [2] + [1, 3] → [2] + [1] + [3] =
[2, 1, 3] - [2] + [3, 1] → [2] + [3] + [1] =
[2, 3, 1] - [3] + [1, 2] → [3] + [1] + [2] =
[3, 1, 2] - [3] + [2, 1] → [3] + [2] + [1] =
[3, 2, 1]
回溯法
那么多一个 以[1, 2, 3, 4]举例, 我们可以这样拆分
- [1] + [2, 3, 4]
- [2] + [1, 3, 4]
- [3] + [1, 2, 4]
- [4] + [1, 2, 3]
后面的3个又可以按上诉方法排序, 那么有
- [1] + [2, 3, 4]
- [1] + [2] + [3, 4]
- [1] + [2] + [4, 3]
- [1] + [3] + [2, 4]
- [1] + [3] + [4, 2]
- [1] + [4] + [2, 3]
- [1] + [4] + [3, 2]
- [2] + [1, 3, 4]
...... - [3] + [1, 2, 4]
...... - [4] + [1, 2, 3]
......
可以不断的循环, 最终变为3元素数组, 3元数组我们又可以仿照上面去处理。多元素数组同理
没太懂的小伙伴可在看一下, 下面翻译版代码, 最好跟一遍循环流程便于更好理解回溯
未翻译版
var res = [[Int]](), c = 0
func permute(_ nums: [Int]) -> [[Int]] {
c = nums.count
backtrack([], nums)
return res
}
func backtrack(_ path: [Int], _ list: [Int]) {
if path.count == c {
res.append(path)
return
}
for i in 0..<list.count {
var temp = list
temp.remove(at: i)
backtrack(path + [list[i]], temp)
}
}
翻译版
// 定义结果res, c为传入数组元素个数, 其实为了后续判断子数组内元素个数
var res = [[Int]](), c = 0
func permute(_ nums: [Int]) -> [[Int]] {
// 定义c为传入数组元素个数
c = nums.count
// 调用统一方法
backtrack([], nums)
// 递归回溯结束, 返回结果
return res
}
// 递归处理统一方法
func backtrack(_ path: [Int], _ list: [Int]) {
// 如果子数组数量等于c说明已加满
if path.count == c {
// 结果添加子数组, 并返回
res.append(path)
return
}
// 未加满, 遍历传入list
for i in 0..<list.count {
// 定义temp为传入list
var temp = list
// 删除当前数组元素
temp.remove(at: i)
// 继续递归, 传入参数为, path + [list[i]], temp
backtrack(path + [list[i]], temp)
// 这里举例便于理解下, 例如 [1, 2, 3]
// 第1次遍历 i = 0, 元素1, temp = [2, 3]
// 传入1.1遍历, 传入参数[] + [1] = [1], temp = [2, 3]
//
// 第1.1次遍历 i = 0, 元素2, temp = [3]
// 传入1.1.1次遍历, 传入参数[1] + [2] = [1, 2], temp = [3]
// 第1.1.1次遍历 i = 0, 元素[1, 2], temp = [3]
// 传入1.1.1.1次遍历, 传入参数[1, 2] + [3] = [1, 2, 3], temp = []
// 传入1.1.1.1次遍历, 传入参数[1, 2, 3], temp = [], 直接走if已加满判断
// res添加[1, 2, 3], 之后返回, 回溯到1.1.1
// 第1.1.1次遍历 i = 1, temp = [3], 无下标为1元素, 结束循环, 回溯到1,1走下一次循环
// 第1.1次遍历 i = 1, 元素3, temp = [2]
// 传入1.1.1次遍历, 传入参数[1] + [3] = [1, 3], temp = [2]
// 传入1.1.1.1次遍历, 传入参数[1, 3] + [2] = [1, 3, 2], temp = []
// 传入1.1.1.1次遍历, 传入参数[1, 3, 2], temp = [], 直接走if已加满判断
// res添加[1, 3, 2], 此时res = [[1, 2, 3], [1, 3, 2]], 之后返回, 回溯到1.1.1
// 第1.1.1次遍历 i = 1, temp = [2], 无下标为1元素, 结束循环, 回溯到1,1走下一次循环
// 第1.1次遍历 i = 2, temp = [2, 3], 无下标为2元素, 结束循环, 回溯到1走下一次循环
// 第1次遍历 i = 1, 元素2, temp = [1, 3]
// 继续之前操作......
}
}
普及知识点
回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确的答案；
- 在尝试了所有可能的分步方法后宣告该问题没有答案。
深度优先搜索算法 （英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
