目录

• 简介
• 78.子集
• 90.子集Ⅱ
• 46.全排列
• 47.全排列Ⅱ
• 挑战题目

简介

回溯法一般都是暴力穷举，时间复杂度O(N!)。通用的模板如下：

const result = [];
const selected = {};
function backtarck(choices: number[], current: number[]) {
    if (满足结束条件) {
        result.add(current)
        return;
    }

    for (const choice in choices) {
        if (!selected[choice]) {
            selected[choice] = true;
            current.push(choice);
            backtrack(选择列表， 路径);
            selected[choice] = false;
            current.pop();
        }
    }
}

78.子集

题目描述

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

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

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

代码

function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const selected: Record<number, boolean> = {};

    function backtrack(start: number, current: number[]) {
        result.push(current.slice());
        if (start > nums.length) {
            return;
        }

        for (let i = start; i < nums.length; i++) {
            const choice = nums[i]
            if (!selected[choice]) {
                selected[choice] = true;
                current.push(choice);
                backtrack(i + 1, current);
                current.pop();
                selected[choice] = false;
            }
        }
    }

    backtrack(0, []);
    return result;
};

90.子集Ⅱ

题目描述

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

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

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

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

代码

function subsetsWithDup(nums: number[]): number[][] {
    const result: number[][] = [];
    const selected = {};

    function backtrack(start: number, curr: number[]) {
        result.push(curr.slice());
        if (curr.length === nums.length) {
            return;
        }

        for (let i = start; i < nums.length; i++) {
            if (selected[i] || (i > 0 && nums[i] === nums[i-1] && !selected[i-1])) {
                continue;
            }

            selected[i] = true;
            curr.push(nums[i]);
            backtrack(i + 1, curr);
            curr.pop();
            selected[i] = false;
        }
    }
    nums.sort((a, b) => a > b ? 1 : -1);
    backtrack(0, []);
    return result;
};

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]]

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

代码

function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const selected = {};

    function backtrack(choices: number[], current: number[]) {
        if (current.length === nums.length) {
            result.push(current.slice());
            return;
        }

        for (const choice of choices) {
            if (!selected[choice]) {
                selected[choice] = true;
                current.push(choice);
                backtrack(choices, current);
                current.pop();
                selected[choice] = false;
            }
        }
    }

    backtrack(nums, []);
    return result;
};

47.全排列Ⅱ

题目描述

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

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

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

代码

function permuteUnique(nums: number[]): number[][] {
    const result: number[][] = [];
    const selected = {};

    function backtrack(choices: number[], current: number[]) {
        if (current.length === nums.length) {
            result.push(current.slice());
            return;
        }

        for (let i = 0; i < choices.length; i++) {
            const cho = choices[i]
            if (selected[i]
                || (i > 0 && choices[i] === choices[i - 1] && !selected[i-1])
            ) {
                continue;
            }

            selected[i] = true;
            current.push(cho);
            backtrack(choices, current);
            current.pop();
            selected[i] = false;
        }
    }

    backtrack(nums.sort((a,b) => a > b ? 1 : -1), []);
    return result;
};

挑战题目

• 17.电话号码的字母组合
• 39.组合总和
• 93.复原IP地址 (有点超纲，像动态规划)
• 131.分割回文串 (有点超纲，像动态规划)