枚举：把有限状态空间走完整｜算法讲义

解决什么问题#

当可行解数量有限、规模不大，而又没有明显的贪心性质或递推结构时，可以把所有候选状态系统地检查一遍。枚举常用于：

从 $n$ 个元素中选择任意子集；
穷举排列、组合或若干离散决策；
为更复杂的算法提供一个容易验证的正确性基线；
在搜索中加入约束和剪枝之前，先明确完整状态空间。

枚举并不等于“随便试”。真正重要的是确定三件事：一个状态怎样表示、每个合法状态是否恰好出现一次，以及检查一个状态需要多少时间。

核心思想与不变量#

对子集问题，每个元素只有“选”和“不选”两种状态。于是一个长度为 $n$ 的二进制数可以唯一表示一个子集：第 $i$ 位为 $1$ 表示选择第 $i$ 个元素。

遍历区间 $[0,2^n)$ 中的所有整数，就会遍历全部子集。循环中的关键不变量是：

进入第 mask 次循环时，所有编号小于 mask 的子集已经被检查，当前二进制位模式唯一对应一个尚未检查的子集。

如果某个部分状态已经违反约束，并且继续加入元素不可能恢复合法性，就可以立即停止检查该状态。这是最简单的剪枝。

复杂度#

共有 $2^n$ 个子集。若每个子集扫描 $n$ 个二进制位，时间复杂度为 $O(n2^n)$ ；模板只维护当前和与最优答案，除输入外额外空间为 $O(1)$ 。

指数复杂度增长很快： $n=25$ 时已经有三千多万个子集，因此枚举前必须先估算状态数。

C++17 模板：位掩码子集枚举#

下面求非负整数集合中“不超过上限的最大子集和”。代码把输入规模限制在 62 以内以避免移位溢出；实际使用朴素枚举时，远小于这个上限就会遇到时间瓶颈。

#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <vector>

using i64 = long long;

struct SubsetResult {
  i64 sum;
  std::uint64_t mask;
};

SubsetResult best_subset_not_exceeding(const std::vector<i64>& values,
                                       i64 limit) {
  if (limit < 0 || values.size() >= 63) {
    throw std::invalid_argument("invalid limit or too many values");
  }
  for (i64 value : values) {
    if (value < 0) {
      throw std::invalid_argument("this template expects non-negative values");
    }
  }

  SubsetResult best{0, 0};
  const std::uint64_t state_count =
      std::uint64_t{1} << static_cast<unsigned>(values.size());

  for (std::uint64_t mask = 0; mask < state_count; ++mask) {
    i64 sum = 0;
    bool feasible = true;

    for (std::size_t i = 0; i < values.size(); ++i) {
      if (((mask >> i) & std::uint64_t{1}) == 0) {
        continue;
      }
      // 所有数非负；一旦超出上限，继续加入元素也无法恢复合法。
      if (values[i] > limit - sum) {
        feasible = false;
        break;
      }
      sum += values[i];
    }

    if (feasible && sum > best.sum) {
      best = {sum, mask};
    }
  }
  return best;
}

int main() {
  const std::vector<i64> values{3, 5, 6};
  const SubsetResult answer = best_subset_not_exceeding(values, 8);

  std::cout << "best sum = " << answer.sum << "\nselected:";
  for (std::size_t i = 0; i < values.size(); ++i) {
    if ((answer.mask >> i) & std::uint64_t{1}) {
      std::cout << ' ' << values[i];
    }
  }
  std::cout << '\n';
}

示例推演#

对集合 {3, 5, 6}，三位掩码依次表示：

`mask`	选择的元素	子集和
`000`	空集	0
`001`	3	3
`010`	5	5
`011`	3, 5	8
`100`	6	6

当上限为 8 时，011 得到最优值 8。后续状态仍会被检查，但不能产生更大的合法结果。

排列枚举与 `std::next_permutation`#

子集枚举回答“选哪些元素”，排列枚举还要回答“按什么顺序放置”。 $n$ 个互不相同元素共有 $n!$ 个排列；若存在重复元素，不同排列数会相应减少。

std::next_permutation(first, last) 将当前序列改成字典序中的下一个排列，并返回 true；若当前已经是最后一个排列，它会把序列重排为第一个排列并返回 false。要完整且不重复地生成所有排列，必须先排序，再使用 do-while，这样初始排列也会被处理。

一次推进最坏扫描 $O(n)$ 个元素，因此枚举 $P$ 个不同排列的总时间为 $O(Pn)$ ，原地变换只需 $O(1)$ 额外空间。

#include <algorithm>
#include <iostream>
#include <vector>

void print_permutation(const std::vector<int>& permutation) {
  for (int value : permutation) {
    std::cout << value << ' ';
  }
  std::cout << '\n';
}

int main() {
  // 排序是完整枚举的起点；重复的 1 不会产生重复排列。
  std::vector<int> permutation{2, 1, 1};
  std::sort(permutation.begin(), permutation.end());

  do {
    print_permutation(permutation);
  } while (std::next_permutation(permutation.begin(), permutation.end()));
}

示例依次输出 1 1 2、1 2 1、2 1 1。如果只想寻找当前序列之后的一个排列，不需要预先排序；排序只是在“枚举全部排列”时用于保证不漏掉更小的字典序状态。

易错点#

写成 1 << n 时，左侧通常是 32 位 int；应根据规模使用 1ULL << n 并先检查移位范围。
同一个组合若用不同选择顺序生成，可能被重复计算。位掩码天然给每个子集唯一编号。
只看“大 O”而不计算实际状态数。指数算法在 $n$ 增加几位后就可能慢一个数量级。
剪枝条件必须具有单调性。本模板依赖所有数非负；若允许负数，“当前和超限”并不代表以后无法恢复。
累加和可能溢出。应根据数据范围选择 long long 或更宽的整数类型。