回溯算法 | note

# 回溯算法

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

# 应用场景

# 算法题：全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

链接：https://leetcode-cn.com/problems/permutations

解题思路：需要所有排列情况；并且没有重复元素；有出路，有思路；考虑使用回溯算法；
解题步骤：首先用递归模拟出所有情况；然后遇到包含重复元素的情况，就回溯；最后收集所有到达递归终点的情况，并返回；

时间复杂度为 O(n!); n! = 1 * 2 * 3 ...(n - 1) * n; 空间复杂度：O(n); 有一个递归；空间复杂度是看临时变量的的结构；

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

# 算法题：子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

链接：https://leetcode-cn.com/problems/subsets

解题思路：求所有子集，没有重复元素；也就是有出路、有思路，可以使用回溯算法；
解题步骤：首先用递归模拟出所有情况，需要保证接的数字都是后面的数字；收集所有到达递归终点的情况，并返回；

时间复杂度为 O(2 ^n); 因为每个元素都有两种可能（存在或不存在）；空间复杂度：O(n); 有一个递归；空间复杂度是看临时变量的的结构；

/**
 * @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 += 1) {
            backtrack(path.concat(nums[i]), l, i + 1);
        }
    }
    for(let i = 0; i <= nums.length; i += 1) {
        backtrack([], i, 0);
    }
    return res;
};

阅读量：

# 回溯算法

# 应用场景

# 算法题：全排列

# 算法题：子集

评 论：

评论：