回溯算法

概念

• 回溯算法是算法设计中的一种方法。
• 回溯算法是一种渐进式寻找并构建问题解决方式的策略。
• 回溯算法会从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。

适用场景

• 有很多条路
• 其中有死路和出路
• 通常需要递归来模拟所有的路

LeetCode：46.全排列

解题思路

• 要求：1.所有的排列情况 2.没有重复元素
• 有出路，有死路
• 考虑使用回溯算法

解题步骤

• 用递归模拟出所有情况
• 遇到包含重复元素的情况，就回溯
• 收集所有到达递归终点的情况，并返回。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const res = []
    const backtrack = (path) => {
        if (path.length === nums.length) {
            res.push(path)
            return
        }
        nums.forEach(n => {
            if (path.includes(n)) return
            backtrack(path.concat(n))
        })
    }
    backtrack([])
    return res

};

46.全排列
时间复杂度： O(n!) n!=1*2*3*...*(n-1) * n
空间复杂度 O(n) n 递归的层数

LeetCode：78.子集

思路

• 要求： 1.所有子集 2.没有重复元素
• 有出路，有死路

解题步骤

• 用递归模拟所有情况
• 保证接的数字都是后面的数字
• 收集所有到达递归终点的情况，并返回。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res = []
    const backtrack = (path, l, start) => {
       if (path.length === l) {
           res.push(path)
           return
       }
       for (let i = start; i < nums.length; i++) {
           backtrack(path.concat(nums[i]), l, i + 1)
       }
    }

    for (let i = 0; i <= nums.length; i++) {
        backtrack([], i, 0)
    }

    return res

};

78.子集
时间复杂度 O(2^N) 因为每个元素都有两种可能（存在或不存在）
空间复杂度 O(N)