46. 全排列
47. 全排列 II
78. 子集
90. 子集 II
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路
递归就像一棵树，画出树状图，比较好理解。
全排列.png
代码
func permute(_ nums: [Int]) -> [[Int]] {
var res = [[Int]]()
var subres = [Int]()
var used = Array.init(repeating: false, count: nums.count)
dfs(nums, 0,&used,&res,&subres)
return res
}
func dfs(_ nums: [Int],_ idx:Int,_ used:inout [Bool],_ res:inout [[Int]],_ subres:inout [Int]) {
if idx == nums.count {
res.append(subres)
return
}
for i in 0..<nums.count {
if used[i] {
continue
}
used[i] = true
subres.append(nums[i])
dfs(nums, idx+1, &used,&res,&subres)
subres.removeLast()
used[i] = false
}
}
47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2]
输出:[[1,1,2],[1,2,1],[2,1,1]]
思路
与全排列1不同的是，有重复数字需要去重。
1.先排序，加去重条件
2.一张图看懂剪枝
全排列2剪枝.png
func permuteUnique(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
var subans = [Int]()
var nums = nums.sorted()
var used = Array.init(repeating: false, count: nums.count)
dfs(&nums, &ans, 0,&used,&subans)
return ans
}
func dfs(_ nums: inout [Int],_ ans:inout [[Int]],_ idx:Int,_ used:inout [Bool],_ subans:inout [Int]) {
if idx == nums.count {
ans.append(subans)
return
}
for i in 0..<nums.count {
if used[i] {
continue
}
if i>0 && nums[i] == nums[i-1] && !used[i-1]{
continue
}
subans.append(nums[i])
used[i] = true
dfs(&nums, &ans, idx+1, &used, &subans)
subans.removeLast()
used[i] = false
}
}
78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
输入: nums = [1,2,3]
输出:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
思路
子集与全排列不同的地方:
dfs(&nums, &ans, idx+1, &used, &subans)
dfs(nums, i+1, &ans, &subans,&used)
读者可自己画出树状图进行理解
代码
//给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
func subsets(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
var subans = [Int]()
var used = Array.init(repeating: false, count: nums.count)
dfs(nums,0,&ans,&subans,&used)
return ans
}
func dfs(_ nums:[Int],_ idx:Int,_ ans:inout [[Int]],_ subans:inout [Int],_ used:inout [Bool]) {
ans.append(subans)
for i in idx..<nums.count {
if used[i] {
continue
}
used[i] = true
subans.append(nums[i])
dfs(nums, i+1, &ans, &subans,&used)
subans.removeLast()
used[i] = false
}
}
90. 子集 II
与全排列2基本一样，递归由idx变成了i。
func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
let nums = nums.sorted()
var ans = [[Int]]()
var subans = [Int]()
var used = Array.init(repeating: false, count: nums.count)
dfs(nums,0,&ans,&subans,&used)
return ans
}
func dfs(_ nums:[Int],_ idx:Int,_ ans:inout [[Int]],_ subans:inout [Int],_ used:inout [Bool]) {
ans.append(subans)
for i in idx..<nums.count {
if used[i] {
continue
}
if i>0 && nums[i] == nums[i-1] && !used[i-1]{//前一个元素没有选过的
continue
}
used[i] = true
subans.append(nums[i])
dfs(nums, i+1, &ans, &subans,&used)
subans.removeLast()
used[i] = false
}
}
总结
- 排列、子集属于递归非常经典的一类问题
- 升级版本就是去重，剪枝
