第 19 站 · 回溯

回溯枚举与去重

选择、递归、撤销；同层跳过重复 O(n · 2^n)

周赛难度分难度分 1342–难度分 1741· 中位难度分 1542（2/12 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 19 站 · 12 题

先学: 树的遍历
学完去: 拆分构造
剪枝搜索
动规入门
面试频次: 2 家公司考过 · 面经出现 2 次LinkedIn 1、Meta 1

先做这道

LC 78子集中等

卡住再看

用选或不选枚举子集，明确每个位置只决策一次。

要点

模板只有三步：做选择、递归、撤销选择；path 是整个搜索共用的一份。
先排序，再用 i > start && nums[i] == nums[i-1] 跳过：同一层不重复选相同的值，更深的层可以。
组合从 start 往后选，避免 {1,2} 和 {2,1} 同时出现；排列每次从头选，用 used 数组标记。

易错点

结果里直接存 path 的引用，回溯结束后所有结果都变成同一个空列表。
把 i > start 写成 i > 0，更深层里合法的重复值也会被跳过。
忘了先排序，相同的值不相邻，去重判断就失效了。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

回溯 · 子集的决策树

列出 [1, 2, 3] 的所有子集

换个输入

当前处理已发现 / 已计算答案

已收集的子集

空

深度: 0
当前路径: {}
结果数: 0

从空集出发，先决定是否选 1。

速度

步骤 1 / 23

始终成立每层决定一个数选或不选；递归返回时撤销这一步，路径恢复原状，再试另一个分支。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 78。

Python

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)  # equal values become neighbours
    res, path = [], []

    def dfs(start: int) -> None:
        res.append(path[:])  # copy: path keeps changing
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # this value was already tried at this level
            path.append(nums[i])
            dfs(i + 1)
            path.pop()  # undo the choice

    dfs(0)
    return res

C++

vector<vector<int>> subsetsWithDup(vector<int> nums) {
    sort(nums.begin(), nums.end());  // equal values become neighbours
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> dfs = [&](int start) {
        res.push_back(path);  // copies path
        for (int i = start; i < (int)nums.size(); i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;  // already tried at this level
            path.push_back(nums[i]);
            dfs(i + 1);
            path.pop_back();  // undo the choice
        }
    };
    dfs(0);
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    List<List<Integer>> subsetsWithDup(int[] nums) {
        this.nums = nums.clone();
        Arrays.sort(this.nums); // equal values become neighbours
        res.clear();
        dfs(0);
        return res;
    }

    private void dfs(int start) {
        res.add(new ArrayList<>(path)); // copy: path keeps changing
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // already tried at this level
            path.add(nums[i]);
            dfs(i + 1);
            path.remove(path.size() - 1); // undo the choice
        }
    }
}

import "sort"

func subsetsWithDup(nums []int) [][]int {
	nums = append([]int(nil), nums...)
	sort.Ints(nums) // equal values become neighbours
	var res [][]int
	var path []int
	var dfs func(start int)
	dfs = func(start int) {
		res = append(res, append([]int(nil), path...)) // copy: path keeps changing
		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue // this value was already tried at this level
			}
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1] // undo the choice
		}
	}
	dfs(0)
	return res
}

常见变体

这一站的题还会用到下面 6 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

变体矩阵：每格写的是决定这一格的那一两行代码
	无重复 · 不复选	有重复 · 不复选	无重复 · 可复选
子集	选或不选：每个下标二选一`dfs(i + 1) # skip nums[i] dfs(i + 1) # take nums[i]dfs(i + 1); // skip nums[i] dfs(i + 1); // take nums[i]dfs(i + 1); // skip nums[i] dfs(i + 1); // take nums[i]dfs(i + 1) // skip nums[i] dfs(i + 1) // take nums[i]`	主模板`if i > start and nums[i] == nums[i - 1]:if (i > start && nums[i] == nums[i - 1]) continue;if (i > start && nums[i] == nums[i - 1]) continue;if i > start && nums[i] == nums[i-1] {`	子集里一个数能无限次重复，答案就有无穷多个，这一格没有意义；加上和或长度的限制，它就成了「组合 · 可复选」。
组合	组合：从 start 往后选，剪掉凑不满的分支`for x in range(start, n - (k - len(path)) + 2):for (int x = start; x <= n - (k - (int)path.size()) + 1; x++) {for (int x = start; x <= n - (k - path.size()) + 1; x++) {for x := start; x <= n-(k-len(path))+1; x++ {`	组合有重复：同层跳过相同值`if i > start and nums[i] == nums[i - 1]: dfs(i + 1, remain - nums[i])if (i > start && nums[i] == nums[i - 1]) continue; dfs(i + 1, remain - nums[i]);if (i > start && nums[i] == nums[i - 1]) continue; dfs(i + 1, remain - nums[i]);if i > start && nums[i] == nums[i-1] { dfs(i+1, remain-nums[i])`	组合可复选：递归时下标不加一`dfs(i, remain - nums[i])dfs(i, remain - nums[i]);dfs(i, remain - nums[i]);dfs(i, remain-nums[i])`
排列	排列：used 数组标记已放的元素`if used[i]:if (used[i]) continue;if (used[i]) continue;if used[i] {`	排列有重复：相同值按原顺序放`if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):if (used[i] \|\| (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))if (used[i] \|\| (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))if used[i] \|\| (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {`	去掉 used 判断，每层都从全部元素里选，长度够 k 就记录，一共 n^k 个序列；LC 17 是每层换一组字母的同一形状。

选或不选：每个下标二选一时间 O(n · 2^n) · 递归深度 O(n)

元素互不相同、要列出所有子集时，最直接的写法是在每个下标上分两支：不选它、选它，走到末尾就是一个子集。LC 78 子集、LC 784 字母大小写全排列都是这个形状。

Python

def subsets(nums: list[int]) -> list[list[int]]:
    """Every subset of distinct nums."""
    res, path = [], []

    def dfs(i: int) -> None:
        if i == len(nums):
            res.append(path[:])  # one leaf per subset
            return
        dfs(i + 1)  # skip nums[i]
        path.append(nums[i])
        dfs(i + 1)  # take nums[i]
        path.pop()

    dfs(0)
    return res

C++

// Every subset of distinct nums.
vector<vector<int>> subsets(const vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> dfs = [&](int i) {
        if (i == (int)nums.size()) {
            res.push_back(path);  // one leaf per subset
            return;
        }
        dfs(i + 1);  // skip nums[i]
        path.push_back(nums[i]);
        dfs(i + 1);  // take nums[i]
        path.pop_back();
    };
    dfs(0);
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    // Every subset of distinct nums.
    List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        res.clear();
        dfs(0);
        return new ArrayList<>(res);
    }

    private void dfs(int i) {
        if (i == nums.length) {
            res.add(new ArrayList<>(path)); // one leaf per subset
            return;
        }
        dfs(i + 1); // skip nums[i]
        path.add(nums[i]);
        dfs(i + 1); // take nums[i]
        path.remove(path.size() - 1);
    }
}

// subsets returns every subset of distinct nums.
func subsets(nums []int) [][]int {
	var res [][]int
	var path []int
	var dfs func(i int)
	dfs = func(i int) {
		if i == len(nums) {
			res = append(res, append([]int(nil), path...)) // one leaf per subset
			return
		}
		dfs(i + 1) // skip nums[i]
		path = append(path, nums[i])
		dfs(i + 1) // take nums[i]
		path = path[:len(path)-1]
	}
	dfs(0)
	return res
}

组合：从 start 往后选，剪掉凑不满的分支时间 O(k · C(n, k)) · 递归深度 O(k)

只要固定大小 k 的组合：每层从 start 往后选，选够 k 个就记录；剩下的数不够凑满 k 个时直接停。LC 77 组合、LC 216 组合总和 III 都用这个剪枝。

Python

def combine(n: int, k: int) -> list[list[int]]:
    """Every k-number combination of 1..n, each in increasing order."""
    res, path = [], []

    def dfs(start: int) -> None:
        if len(path) == k:
            res.append(path[:])
            return
        for x in range(start, n - (k - len(path)) + 2):  # leave room for the rest
            path.append(x)
            dfs(x + 1)
            path.pop()

    dfs(1)
    return res

C++

// Every k-number combination of 1..n, each in increasing order.
vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> dfs = [&](int start) {
        if ((int)path.size() == k) {
            res.push_back(path);
            return;
        }
        for (int x = start; x <= n - (k - (int)path.size()) + 1; x++) {  // leave room for the rest
            path.push_back(x);
            dfs(x + 1);
            path.pop_back();
        }
    };
    dfs(1);
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int n, k;

    // Every k-number combination of 1..n, each in increasing order.
    List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        res.clear();
        dfs(1);
        return new ArrayList<>(res);
    }

    private void dfs(int start) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int x = start; x <= n - (k - path.size()) + 1; x++) { // leave room for the rest
            path.add(x);
            dfs(x + 1);
            path.remove(path.size() - 1);
        }
    }
}

// combine returns every k-number combination of 1..n, each in increasing order.
func combine(n, k int) [][]int {
	var res [][]int
	var path []int
	var dfs func(start int)
	dfs = func(start int) {
		if len(path) == k {
			res = append(res, append([]int(nil), path...))
			return
		}
		for x := start; x <= n-(k-len(path))+1; x++ { // leave room for the rest
			path = append(path, x)
			dfs(x + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(1)
	return res
}

组合可复选：递归时下标不加一时间指数级，取决于 target / min · 递归深度 O(target / min)

同一个数可以选多次：递归时传 i 而不是 i + 1。先排序，候选数一旦超过剩余目标就 break，后面更大的数也不用试。LC 39 组合总和就是这一格。

Python

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """Distinct positive candidates, each reusable: every multiset that sums to target."""
    nums = sorted(candidates)
    res, path = [], []

    def dfs(start: int, remain: int) -> None:
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:
                break  # sorted: every later candidate is too big as well
            path.append(nums[i])
            dfs(i, remain - nums[i])  # i, not i + 1: the same number may come again
            path.pop()

    dfs(0, target)
    return res

C++

// Distinct positive candidates, each reusable: every multiset that sums to target.
vector<vector<int>> combinationSum(vector<int> nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> path;
    function<void(int, int)> dfs = [&](int start, int remain) {
        if (remain == 0) {
            res.push_back(path);
            return;
        }
        for (int i = start; i < (int)nums.size(); i++) {
            if (nums[i] > remain) break;  // sorted: every later candidate is too big as well
            path.push_back(nums[i]);
            dfs(i, remain - nums[i]);  // i, not i + 1: the same number may come again
            path.pop_back();
        }
    };
    dfs(0, target);
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    // Distinct positive candidates, each reusable: every multiset that sums to target.
    List<List<Integer>> combinationSum(int[] candidates, int target) {
        nums = candidates.clone();
        Arrays.sort(nums);
        res.clear();
        dfs(0, target);
        return new ArrayList<>(res);
    }

    private void dfs(int start, int remain) {
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > remain) break; // sorted: every later candidate is too big as well
            path.add(nums[i]);
            dfs(i, remain - nums[i]); // i, not i + 1: the same number may come again
            path.remove(path.size() - 1);
        }
    }
}

import "sort"

// combinationSum returns every multiset of the distinct, reusable candidates that sums to target.
func combinationSum(candidates []int, target int) [][]int {
	nums := append([]int(nil), candidates...)
	sort.Ints(nums)
	var res [][]int
	var path []int
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i := start; i < len(nums); i++ {
			if nums[i] > remain {
				break // sorted: every later candidate is too big as well
			}
			path = append(path, nums[i])
			dfs(i, remain-nums[i]) // i, not i + 1: the same number may come again
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}

组合有重复：同层跳过相同值时间 O(n · 2^n) · 递归深度 O(n)

输入里有重复数字、每个只能用一次、答案不能重复：排序后同一层遇到和前一个相同的值就跳过，递归传 i + 1。LC 40 组合总和 II 就是这一格。

Python

def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    """Each candidate used at most once; repeats in the input, no repeated answers."""
    nums = sorted(candidates)
    res, path = [], []

    def dfs(start: int, remain: int) -> None:
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:
                break
            if i > start and nums[i] == nums[i - 1]:
                continue  # this value was already tried at this level
            path.append(nums[i])
            dfs(i + 1, remain - nums[i])
            path.pop()

    dfs(0, target)
    return res

C++

// Each candidate used at most once; repeats in the input, no repeated answers.
vector<vector<int>> combinationSum2(vector<int> nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> path;
    function<void(int, int)> dfs = [&](int start, int remain) {
        if (remain == 0) {
            res.push_back(path);
            return;
        }
        for (int i = start; i < (int)nums.size(); i++) {
            if (nums[i] > remain) break;
            if (i > start && nums[i] == nums[i - 1]) continue;  // already tried at this level
            path.push_back(nums[i]);
            dfs(i + 1, remain - nums[i]);
            path.pop_back();
        }
    };
    dfs(0, target);
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    // Each candidate used at most once; repeats in the input, no repeated answers.
    List<List<Integer>> combinationSum2(int[] candidates, int target) {
        nums = candidates.clone();
        Arrays.sort(nums);
        res.clear();
        dfs(0, target);
        return new ArrayList<>(res);
    }

    private void dfs(int start, int remain) {
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > remain) break;
            if (i > start && nums[i] == nums[i - 1]) continue; // already tried at this level
            path.add(nums[i]);
            dfs(i + 1, remain - nums[i]);
            path.remove(path.size() - 1);
        }
    }
}

import "sort"

// combinationSum2 uses each candidate at most once and returns no repeated answers.
func combinationSum2(candidates []int, target int) [][]int {
	nums := append([]int(nil), candidates...)
	sort.Ints(nums)
	var res [][]int
	var path []int
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i := start; i < len(nums); i++ {
			if nums[i] > remain {
				break
			}
			if i > start && nums[i] == nums[i-1] {
				continue // this value was already tried at this level
			}
			path = append(path, nums[i])
			dfs(i+1, remain-nums[i])
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}

排列：used 数组标记已放的元素时间 O(n · n!) · 空间 O(n)

顺序不同算不同答案时，每层都从头扫一遍，跳过已经用过的位置。LC 46 全排列就是这一格；每层换一组候选（LC 17 电话号码的字母组合）也是同一个骨架。

Python

def permute(nums: list[int]) -> list[list[int]]:
    """Every ordering of distinct nums."""
    res, path, used = [], [], [False] * len(nums)

    def dfs() -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue  # each element appears once per ordering
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return res

C++

// Every ordering of distinct nums.
vector<vector<int>> permute(const vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    function<void()> dfs = [&]() {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for (size_t i = 0; i < nums.size(); i++) {
            if (used[i]) continue;  // each element appears once per ordering
            used[i] = true;
            path.push_back(nums[i]);
            dfs();
            path.pop_back();
            used[i] = false;
        }
    };
    dfs();
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;
    private boolean[] used;

    // Every ordering of distinct nums.
    List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        used = new boolean[nums.length];
        res.clear();
        dfs();
        return new ArrayList<>(res);
    }

    private void dfs() {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // each element appears once per ordering
            used[i] = true;
            path.add(nums[i]);
            dfs();
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

// permute returns every ordering of distinct nums.
func permute(nums []int) [][]int {
	var res [][]int
	var path []int
	used := make([]bool, len(nums))
	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i, x := range nums {
			if used[i] {
				continue // each element appears once per ordering
			}
			used[i] = true
			path = append(path, x)
			dfs()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs()
	return res
}

排列有重复：相同值按原顺序放时间 O(n · n!) · 空间 O(n)

输入有重复、排列不能重复：排序后规定相同的值只能按输入顺序放，前一个相同值还没用时跳过当前这个。LC 47 全排列 II、LC 1079 活字印刷都靠这一行去重。

Python

def permute_unique(nums: list[int]) -> list[list[int]]:
    """Every distinct ordering when nums has repeats."""
    nums = sorted(nums)
    res, path, used = [], [], [False] * len(nums)

    def dfs() -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                continue  # equal values are placed in input order only
            used[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return res

C++

// Every distinct ordering when nums has repeats.
vector<vector<int>> permuteUnique(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    function<void()> dfs = [&]() {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for (size_t i = 0; i < nums.size(); i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
                continue;  // equal values are placed in input order only
            used[i] = true;
            path.push_back(nums[i]);
            dfs();
            path.pop_back();
            used[i] = false;
        }
    };
    dfs();
    return res;
}

Java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;
    private boolean[] used;

    // Every distinct ordering when nums has repeats.
    List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums.clone();
        Arrays.sort(this.nums);
        used = new boolean[nums.length];
        res.clear();
        dfs();
        return new ArrayList<>(res);
    }

    private void dfs() {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
                continue; // equal values are placed in input order only
            used[i] = true;
            path.add(nums[i]);
            dfs();
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

import "sort"

// permuteUnique returns every distinct ordering when nums has repeats.
func permuteUnique(input []int) [][]int {
	nums := append([]int(nil), input...)
	sort.Ints(nums)
	var res [][]int
	var path []int
	used := make([]bool, len(nums))
	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i := range nums {
			if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
				continue // equal values are placed in input order only
			}
			used[i] = true
			path = append(path, nums[i])
			dfs()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs()
	return res
}

为什么对

搜索树的每个节点对应一个部分解。「选择 → 递归 → 撤销」保证从子节点返回时 path 恢复原样，兄弟分支看到的状态互不干扰。
组合从 start 往后选，等于强制下标递增，而每个组合只有一种递增排列，所以恰好生成一次，不重不漏。
去重条件 i > start && nums[i] == nums[i−1]：排序后相同的值相邻，同一层只让第一个展开，它的子树已经包含了后面那些相同值能得到的全部结果。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

枚举子集、组合、排列，我用回溯三步：选择、递归、撤销。path 是整个搜索共用的一个缓冲区，撤销保证兄弟分支互不干扰。组合从 start 往后选，强制下标递增，每个组合只出现一次；有重复元素就先排序，同一层跳过和前一个相同的值。复杂度和答案数量同阶，比如子集是 O(n · 2^n)。

English

For subsets, combinations and permutations I backtrack in three moves: choose, recurse, undo. path is one buffer shared by the whole search, and undoing keeps sibling branches independent. Combinations pick from start onward, so indexes increase and each combination appears once; with duplicates I sort and skip a value equal to the previous one on the same level. The cost matches the output size, for example O(n · 2^n) for subsets.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

搜索树的每个节点对应一个部分解。「选择 → 递归 → 撤销」保证从子节点返回时 path 恢复原样，兄弟分支看到的状态互不干扰。
组合从 start 往后选，等于强制下标递增，而每个组合只有一种递增排列，所以恰好生成一次，不重不漏。
去重条件 i > start && nums[i] == nums[i−1]：排序后相同的值相邻，同一层只让第一个展开，它的子树已经包含了后面那些相同值能得到的全部结果。

小测

4 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

4 道题

用回溯生成 n 个不同元素的所有子集，每个子集都复制成一个列表输出。总时间是？
- O(2^n)
- O(n!)
- O(n·2^n)
- O(n²)
生成 [1, 1, 2] 的不重复全排列，常用规则是：先排序，在同一层里遇到 nums[i] == nums[i-1] 且 nums[i-1] 没有被使用时跳过 nums[i]。这条规则保证了什么？
- 相等的元素总是按原来的先后顺序放入排列，所以每种排列只生成一次
- 相等的元素永远不会相邻
- 排列按字典序倒序输出
- 可以省去 used 数组

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def subsets(a):
    out = []

    def go(i, cur):
        if i == len(a):
            out.append(cur[:])
            return
        go(i + 1, cur)
        cur.append(a[i])
        go(i + 1, cur)
        cur.pop()

    go(0, [])
    return out

O(n²)
O(n!)
O(n·2^n)
O(2^n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def perms(a):
    out = []
    used = [False] * len(a)

    def go(cur):
        if len(cur) == len(a):
            out.append(cur[:])
            return
        for i in range(len(a)):
            if not used[i]:
                used[i] = True
                cur.append(a[i])
                go(cur)
                cur.pop()
                used[i] = False

    go([])
    return out

O(n·n!)
O(n!)
O(2^n)
O(n^n)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

def subsets_with_dup(nums: list[int]) -> list[list[int]]:

分档练习

本站在 500 路里的 12 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 5

#	题目	一句话思路	难度分
78	子集	用选或不选枚举子集，明确每个位置只决策一次。
77	组合	枚举固定大小组合，用剩余位置数量剪枝。
46	全排列	通过使用标记枚举排列，区分路径顺序与元素集合。
17	电话号码的字母组合	按位置展开多个字符候选，练习多层选择树。
784	字母大小写全排列	逐字符选择大小写，区分字母分支与数字的单一分支。	难度分 1342

核心 7

#	题目	一句话思路	难度分
90	子集 II	排序后跳过同层重复值，保证重复元素子集不重复输出。
47	全排列 II	在排列中处理重复元素，区分同层去重与跨层重复使用。
39	组合总和	控制起始位置允许重复选取，同时避免同一组合的不同顺序。
40	组合总和 II	每个候选位置最多使用一次，结合排序、剪枝和同层去重。
216	组合总和 III	同时约束选择数量、和值与递增候选范围。
1079	活字印刷	用字符频次数组枚举不同非空序列，避免重复字母导致重复计数。	难度分 1741
491	非递减子序列	保持原下标顺序枚举非递减子序列，用每层集合去重。

本站 OA 真题 6

Work Schedule — Fill Question Marks to Match TotalSnowflake
Closest Subsequence SumSalesforce
Find Minimum Cost to Shift MachinesCisco
Reach Target BalanceConfluent
Work Schedules (for MTS2)Nutanix
Maximum Strings Buildable from at Most K LettersDeloitte

全部 6 道