枚举就是[ 不遗漏 - 不重复 - 高效 ]

登录以参加训练计划

枚举是什么

枚举就是

1. 不遗漏
2. 不重复
3. 高效

接下来我们一个一个说。

不重复

基本结构就是维持一个可选的集合($candidates$)、当前已选的部分($prefix$)、剩余可选数量($remain$)。 每次递归就是从$candidates$里面每个都选一遍 ($0 ≤ i ≤ len(candidates) - 1$)，选一个出来添加到prefix的最后，可选数量减少一个。

核心代码模版应该是这样的：

def solve(candidates, prefix, remain):

    if remain == 0:
        # 这里应该是本次选完了，产生结果
        pass


    for i in range(len(candidates)):
        # 可选集合不变
        # 已选部分多了第i号
        # 剩余可选数量少了一个
        solve(candidates, prefix + candidate[i], remain - 1)

solve(candidates, [], remain)

void solve(vector<int> & candidates, vector<int> & prefix, int remain) {
    if (remain == 0) {
        // 这里应该是本次选完了，产生结果
    }

    for (int i = start_index; i < candidates.size(); i++) {
        prefix.push_back(candidates[i]);
        solve(candidates, prefix, i + 1, remain - 1);
        prefix.pop_back();
    }

}
vector<int> prefix;
solve(candidates, prefix, remain);

不重复

如果需要去重，有两个方案：

1. 有序枚举
2. 集合

方案	优点	缺点
有序枚举	去掉了不必要的递归分支，运行相对快	要想到怎么把后选项排序避免重复枚举
集合	好写，在上一个方案中用集合收集所有的枚举值就能去重	慢，可能卡大数据得分点

有序枚举

基本的思路就是让候选项是有序的，从小到大选，prefix中只会出现[1,2,4]，而不会出现[1,4,2]这样的办法来避免重复。

基本结构就是维持一个可选的集合($candidates$)、当前已选的部分($prefix$)、可选项的最小索引($start\_index$)、剩余可选数量($remain$)。 每次递归就是从$candidates$里面从$start\_index$开始($start\_index ≤ i ≤ len(candidates) - 1$)，选一个出来放到$prefix$的最后，更新下可选项最小索引、和可选数量

核心代码模版应该是这样的：

def solve(candidates, prefix, start_index, remain):

    if remain == 0:
        # 这里应该是本次选完了，产生结果
        pass


    for i in range(start_index, len(candidates)):
        # 可选集合不变
        # 已选部分多了第i号
        # 可选项最小索引是当前选的下一位 （ 不能往前选 ）
        # 剩余可选数量少了一个
        solve(candidates, prefix + candidate[i], i + 1, remain - 1)

candidates.sort()
solve(candidates, [], 0, remain)

void solve(vector<int> & candidates, vector<int> & prefix, int start_index, int remain) {
    if (remain == 0) {
        // 这里应该是本次选完了，产生结果
    }

    for (int i = start_index; i < candidates.size(); i++) {
        prefix.push_back(candidates[i]);
        solve(candidates, prefix, i + 1, remain - 1);
        prefix.pop_back();
    }

}

集合的方案

result = set()

def solve(candidates, prefix, remain):

    if remain == 0:
        # 这里应该是本次选完了，产生结果
        # 加到几集合中，自带去重。
        # 但请注意[1,2,1] 和 [1,1,2] 是两个列表
        # 如果题目认为是重复的话，可以先prefix.sort()在add，就能避免了
        result.add(prefix)

    for i in range(len(candidates)):
        # 可选集合不变
        # 已选部分多了第i号
        # 剩余可选数量少了一个
        solve(candidates, prefix + candidate[i], remain - 1)

solve(candidates, [], 0, remain)

unordered_set<vector<int>> results;

void solve(vector<int> & candidates, vector<int> & prefix, int start_index, int remain) {
    if (remain == 0) {
        // 这里应该是本次选完了，产生结果
        result.insert(prefix);
    }

    for (int i = start_index; i < candidates.size(); i++) {
        prefix.push_back(candidates[i]);
        solve(candidates, prefix, i + 1, remain - 1);
        prefix.pop_back();
    }

}
vector<int> prefix;
solve(candidates, prefix, 0, remain);

高效

有一类型的数据，即是用上了有序枚举，都会超时。你知道是什么吗？

例： 有1,000,000,000,000,000个硬币，每个硬币都是1块钱，问，选三个出来，得到的不同的和是什么？

瞪眼就知道只有1种，是3，但是用上面的有序枚举模版，仍然会超时，为什么呢？

因为在求不同和的前提下，第一个硬币和第1,000,000,000,000,000个硬币，效果是等价的，都是为这个和增加1，所以我们在每一步枚举的时候，不应该去做中间无用的999,999,999,999,999次枚举。