建模。「下一个排列」= 恰好比当前大的最小排列。按 s-009-3 的四步：找最右升序对定 pivot、在后缀找大于 pivot 的最小元素、交换、反转后缀。正确性三句话：后缀非升说明前缀不动时已到顶；字典序前面的位置优先，所以保住最长前缀、只推进位置 i；推进幅度取最小（successor），其余元素排成最小序（反转后缀）。

bool nextPerm(vector<int>& a) {              // 返回 false 表示已是最大排列
    int n = (int)a.size(), i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) --i;  // 1) 最右升序相邻对的前一个下标
    if (i < 0) {                              // 整个数组非升：已是字典序最大
        reverse(a.begin(), a.end());          // 翻回最小，进入下一轮循环
        return false;
    }
    int j = n - 1;
    while (a[j] <= a[i]) --j;                // 2) 从右向左第一个大于 a[i] 的元素
    swap(a[i], a[j]);                         // 3) 最小可行「进位」
    reverse(a.begin() + i + 1, a.end());      // 4) 后缀反转为非降，即最小排列
    return true;
}

用法即 do-while 循环：sort(a.begin(), a.end()); do { emit(a); } while (nextPerm(a));，从最小排列不重不漏走完全部相异排列。

数值走查。取 \(a = [1, 5, 8, 4, 7, 6, 5, 3, 1]\)：第一步从右扫，3 与 1 非升、5 与 3 非升、6 与 5 非升、7 与 6 非升，到 \(a_3 = 4 \lt a_4 = 7\) 停下，pivot 下标 \(i = 3\)；第二步从右找第一个大于 4 的元素，跳过 1、3、再到 \(a_6 = 5\) 停下，\(j = 6\)（注意后缀非升保证 5 正是「大于 4 的最小值」，且重复的 5 不会造成歧义）；第三步交换得 \([1, 5, 8, 5, 7, 6, 4, 3, 1]\)；第四步反转下标 4 起的后缀 \([7,6,4,3,1] \to [1,3,4,6,7]\)，最终 \([1, 5, 8, 5, 1, 3, 4, 6, 7]\)。再如 \([3,2,1]\)：找不到升序对，返回 false 并翻转为 \([1,2,3]\)。三元素完整圈：123 → 132 → 213 → 231 → 312 → 321 → 回到 123。

复杂度与边界。单次最坏 \(O(n)\)、均摊 \(O(1)\)（全枚举期望扫描 \(e - 1 \approx 1.72\) 位，s-009-3 已推导）；空间 \(O(1)\)，纯原地。边界：单元素（i 初始为 −1，直接翻回自身，正确）；全相等元素（同理，只产生一个排列）；已是最大（返回 false 语义要向调用方说明）；重复元素由严格比较自动折叠，无需额外去重代码。

面试怎么讲。先讲进位类比：「找最后一个还能进位的位置，用最小的幅度进位，其余部分重置为最小」。写完代码立刻用 [1,2,3] 走一圈验证，再主动补均摊分析——「枚举全圈的期望扫描长度是 \(e - 1\)，均摊 O(1)」是让考官记住你的那一句。

建模。重复的根源是决策树里存在「同一层、等价选择」的分支：前缀相同、本轮分别选第 1 个 1 或第 2 个 1，产生的子树完全一样。剪枝策略：排序使相同元素相邻，并规定同值元素必须按索引顺序进入路径——在某层若 \(a_i = a_{i-1}\) 而 \(a_{i-1}\) 尚未进入路径（used[i-1] 为 false），说明正在尝试「跳过前一个、选当前这个」，这与「选前一个、跳过当前」等价，剪掉当前分支。

vector<vector<int>> permuteUnique(vector<int>& a) {
    sort(a.begin(), a.end());            // 去重前提：同值元素相邻
    res.clear(); path.clear();
    used.assign(a.size(), false);
    backtrackDup(a);
    return res;
}

void backtrackDup(vector<int>& a) {
    if (path.size() == a.size()) { res.push_back(path); return; }
    for (int i = 0; i < (int)a.size(); ++i) {
        if (used[i]) continue;           // 已在路径上
        // 同层剪枝：与前一元素同值、且它还没被选，则当前分支是等价重复
        if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
        used[i] = true; path.push_back(a[i]);
        backtrackDup(a);
        path.pop_back(); used[i] = false;
    }
}

数值走查。\(a = [1, 1, 2]\)（已排序）。根层候选 1（第 0 个）、1（第 1 个）、2：选第 0 个 1 合法；轮到第 1 个 1 时因 \(a_1 = a_0\) 且 used[0] 为 false 被剪；选 2 合法。如此展开，最终恰好得到 \([1,1,2]\)、\([1,2,1]\)、\([2,1,1]\) 三个排列——与多重集公式 \(\frac{3!}{2! \cdot 1!} = 3\) 一致，朴素模板会输出 6 个（每个重复一次）。

与 next_permutation 对照。两方案共享同一原理「定序消等价」：回溯版在决策树上按层剪枝，字典序版在最终排列的全序上只走相邻相异排列。工程选择看需求：要迭代产出、断点续跑、或输入基本有序，用 next_permutation（均摊 O(1) 一格）；要按树形结构加更多约束（如剪掉不满足条件的分支），用回溯。子集的去重同型：排序后条件改写为 i > start && a[i] == a[i-1] 时跳过（对应 LeetCode 90，[1,2,2] 得 6 个子集），与例题 2 同型，仅「对象从排列换成子集、start 取代 used 作层标识」不同。

复杂度与边界。时间 \(O(n \cdot k)\)，其中 \(k = \frac{n!}{\prod_j c_j!}\) 是相异排列数（输出敏感）；空间 \(O(n)\) 递归深度加 used。边界：全相等元素（\(k = 1\)，剪枝保证只输出一次）；空数组（返回仅含空排列或空集，按题意定义）；必须先排序，否则剪枝条件失效；swap 型排列写法配去重极易出错（需要按值去重的集合判定），面试别冒险。

面试怎么讲。先画 [1,1,2] 的两层树指出重复分支，再给剪枝条件并强调「规定同值元素的入选次序」这一不变量；最后补一句对照——「也可以排序后反复调用 next_permutation，重复元素自动折叠」，展示你把 s-009-3 与 s-009-2 串成了一条线。

(a) 判 2 的幂。2 的幂的二进制恰有一个 1 位（\(2^k = (1\underbrace{0\ldots0}_{k})_2\)），x & (x - 1) 恰好消去最低位的 1：若 x 只有这一个 1，结果为 0。因此判定式是「非零且清最低位后归零」。陷阱：用有符号 int 时守卫必须写 x > 0——INT_MIN 的位模式 \((1000\ldots0)_2\) 清最低位后也是 0，会被误判为「2 的幂」，而它根本是负数；若以 unsigned 视角，\(2^{31}\) 确实是 2 的幂，判定应当为真。结论对错取决于「你声明的是什么类型」，这本身就是符号数考点的活例子。

(b) 统计位 1。Brian Kernighan 写法每轮消一个 1，循环次数恰为 popcount，最坏仍 \(O(w)\) 但对稀疏位模式极快；标准工具是 __builtin_popcount 与 C++20 的 std::popcount（多数 CPU 有 POPCNT 指令，O(1)）。

(c) 枚举 x 的子集。循环 s = (s - 1) & x 从 x 出发按数值递减走遍每个子集；lowbit 视角看每一站的变化：s - 1 借位减掉 s 的最低位 1（设其在第 t 位），第 t 位变 0、更低位全变 1，再与 x 相与抹掉不属于 x 的位——相当于「x 位域内的减一」。

bool isPowerOfTwo(uint32_t x) {          // (a) 2 的幂恰有一个 1 位
    return x != 0 && (x & (x - 1)) == 0;
}   // 若参数是 int，守卫必须写成 x > 0，防 INT_MIN 误判

int popcount(uint32_t x) {              // (b) 每消一个 1 循环一次
    int c = 0;
    while (x) { x &= x - 1; ++c; }      // 清最低位的 1
    return c;
}

void enumerateSubmasks(uint32_t x) {    // (c) x 的全部子集（含 0 与 x）
    for (uint32_t s = x; ; s = (s - 1) & x) {
        visit(s);                       // 依数值递减次序出现
        if (s == 0) break;              // 空集是终点，漏判即死循环
    }
}

数值走查。取 \(x = (10110)_2 = 22\)（popcount 为 3，应有 \(2^3 = 8\) 个子集）：22 → (21)&22 = \((10101)_2 \mathbin{\&} (10110)_2 = (10100)_2 = 20\) → (19)&22 = 18 → (17)&22 = 16 → (15)&22 = 6 → (5)&22 = 4 → (3)&22 = 2 → (1)&22 = 0，共 8 站：{22, 20, 18, 16, 6, 4, 2, 0}，恰为位域 {1,2,4} 上的全部组合、严格递减、无一重复。

复杂度与边界。(a) \(O(1)\)；(b) \(O(\mathrm{popcount})\)；(c) \(O(2^{\mathrm{popcount}(x)})\)，全部 x 的子集总枚举量 \(3^n\)。边界：x = 0（(c) 只访问空集一次即退出）；n 较大时掩码用 1ull << n 或 unsigned long long（1 << 31 在 int 上已是负数）；(a) 的类型口径（int 还是 unsigned）先声明再作答。

面试怎么讲。三题共用一句话开场：「2 的幂、位 1 计数、子集枚举都是对『最低位的 1』做文章——清它、数它、或借它减一」。lowbit 与清最低位的表达式顺手写出补码解释（\(-x = \sim x + 1\)），把 s-009-5 的知识与位技巧焊在一起。

建模。无符号加法是模 \(2^{32}\) 的时钟算术：数学和若达 \(2^{32}\) 即绕回。有符号溢出则无任何数学保证——直接触发 UB。追踪三类现象需要的是同一条公式：环绕值 = 数学和减去足够的 \(2^{32}\) 使其落回 \([0, 2^{32})\)。

uint32_t a = 4000000000u, b = 500000000u;
uint32_t c = a + b;    // 数学和 4,500,000,000 >= 2^32 = 4,294,967,296
// 环绕：c = 4,500,000,000 - 4,294,967,296 = 205,032,704（良定义）

int x = -1;
unsigned u = 1u;
bool r = x < u;        // false：x 先转换为 4,294,967,295u 再比较

int m = INT_MIN;       // -2147483648
// int y = -m;         // UB：数学值 +2^31 无法用 int 表示
unsigned uu = (unsigned)m;      // 安全：得到 2^31 = 2147483648u
long long y = -(long long)m;    // 安全：得到 +2147483648LL

数值追踪。(1) \(a + b\)：数学和 \(4{,}500{,}000{,}000\)，减一圈 \(2^{32} = 4{,}294{,}967{,}296\) 得 205,032,704——无符号下这是正确结果而非错误，但拿去做「和是否超过 4.29e9」这类判断就会全盘皆错。(2) -1 < 1u：混算把 −1 按补码位模式 \(0xFFFFFFFF\) 转为 4,294,967,295u，比较 4294967295 与 1，结果 false；同理 v.size() - 1 当 v 为空时是 SIZE_MAX，反向 for 循环 i >= 0 永真而死循环。(3) -INT_MIN：补码位模式 \(0x80000000\) 取负仍得 \(0x80000000\)（机器层面），语义层面是 UB；abs(INT_MIN) 同罪。LeetCode 7「整数反转」在这栽跟头的实现数不胜数。

正确的溢出检测。原则「先判后算，用范围或位，不用加法结果反推」：

bool addOverflows(int a, int b) {              // 有符号：预判
    if (b > 0 && a > INT_MAX - b) return true; // 上溢：先算安全的 INT_MAX - b
    if (b < 0 && a < INT_MIN - b) return true; // 下溢
    return false;
}   // 或 __builtin_add_overflow(a, b, &sum)：一条内建搞定加减乘

bool unsignedAddOverflows(unsigned a, unsigned b) {  // 无符号：环绕良定义
    return a + b < a;    // 环绕必然变小，此比较合法且常被编译器保留
}

怎么读：有符号的 a + b < a 会被编译器依「不溢出」假设优化成 false（例：addOverflowsBad），必须预判；无符号的环绕是定义的一部分，「和小于加数」反而是合法且可靠的上溢信号——同一表达式在两种符号性下命运迥异，正是源题库强调 difference 的原因。

边界与工具。涉及可能过界的中间量，统一升宽（int → long long、unsigned → unsigned long long）后再算；测试期开 UBSan（-fsanitize=undefined）让有符号溢出当场报错；审阅重点盯三类位置——反向循环的下界、size() 参与的减法、对任意输入取负/求绝对值。

面试怎么讲。开口先立框架：「无符号是模 \(2^w\) 的良定义环绕，有符号溢出是 UB，混算先转无符号」，然后逐个报数：4e9 + 5e8 = 205,032,704；−1 转 unsigned 后比较为 false；−INT_MIN 是 UB。最后给守门三件套：升宽、先判后算、UBSan。能把三件事用「同一串比特、两种契约」串起来，就是满分结构。