算法设计思想-回溯算法

1. 是什么

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

2. 场景

• 有很多路。
• 这些路里，有死路，也有出路。
• 通常需要递归来模拟所有的路。

2.1. 全排列 leetCode 46

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

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

时间复杂度:O(n!)
空间复杂度: O(n) n 为 nums的长度

2.2. 子集 leetCode 78

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

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

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