回溯法
回溯法(backtrack)常用于遍历列表所有子集,是 DFS 深度搜索一种,一般用于全排列,穷尽所有可能,遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!),它不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。
result = []
func backtrack(选择列表,路径):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(选择列表,路径)
撤销选择
核心就是从选择列表里做一个选择,然后一直递归往下搜索答案,如果遇到路径不通,就返回来撤销这次选择。
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
遍历过程

image.png
//回溯
//https://leetcode-cn.com/problems/subsets/solution/swift-zi-ji-hui-su-by-hu-cheng-he-da-bai-sha/
//执行用时:8 ms, 在所有 Swift 提交中击败了97.96%的用户
//内存消耗:13.5 MB, 在所有 Swift 提交中击败了93.90%的用户
func subsets(_ nums: [Int]) -> [[Int]] {
var res = [[Int]]()