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
            }
        }

总结

1. 排列、子集属于递归非常经典的一类问题
2. 升级版本就是去重，剪枝