Skip to content

Latest commit

 

History

History
149 lines (124 loc) · 4.62 KB

回溯法.md

File metadata and controls

149 lines (124 loc) · 4.62 KB
Raw

回溯法

背景

回溯法（backtrack）常用于遍历列表所有子集，是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!)，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

模板

result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择

核心就是从选择列表里做一个选择，然后一直递归往下搜索答案，如果遇到路径不通，就返回来撤销这次选择。

示例

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

function subsets(nums: number[]): number[][] {
    const res: number[][] = []
    helper(0, nums, res, [])
    return res
};
function helper(i: number, nums: number[], res: number[][], tmp: number[]): void {
    res.push([].concat(tmp))
    for (let j = i; j < nums.length; j++) {
        tmp.push(nums[j])
        helper(j + 1, nums, res, tmp)
        tmp.pop()
    }
}
90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

function subsetsWithDup(nums: number[]): number[][] {
    const res: number[][] = []
    nums = nums.sort()
    helper(0, nums, res, [])
    return res
};
function helper(i: number, nums: number[], res: number[][], tmp: number[]): void {
    res.push([].concat(tmp))
    for (let j = i; j < nums.length; j++) {
        if (j > i && nums[j] === nums[j - 1]) {
            continue
        }
        tmp.push(nums[j])
        helper(j + 1, nums, res, tmp)
        tmp.pop()
    }
}
46. 全排列

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

function permute(nums: number[]): number[][] {
    const res: number[][] = []
    const templist: number[] = []
    const visited: boolean[] = new Array(nums.length).fill(false)
    backTrack(nums, res, templist, visited)
    return res
};

function backTrack(nums, res, templist, visited) {
    if (templist.length === nums.length) {
        res.push([].concat(templist))
        return
    }
    for (let i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue
        }
        templist.push(nums[i])
        visited[i] = true
        backTrack(nums, res, templist, visited)
        visited[i] = false
        templist.pop(nums[i])
    }
}
47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

function permuteUnique(nums: number[]): number[][] {
    nums = nums.sort((a, b) => a - b)
    const res: number[][] = []
    const templist: number[] = []
    const visited: boolean[] = new Array(nums.length).fill(false)
    backTrack(nums, res, templist, visited)
    return res
};

function backTrack(nums, res, templist, visited) {
    if (templist.length === nums.length) {
        res.push([].concat(templist))
        return
    }
    for (let i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue
        }
        if (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1]) {
            continue
        }
        templist.push(nums[i])
        visited[i] = true
        backTrack(nums, res, templist, visited)
        visited[i] = false
        templist.pop(nums[i])
    }
}

练习

挑战题目