算法思想 - 枚举算法

1. 枚举算法理论

枚举算法（Brute Force 或 Enumeration） 是一种最朴素、最直接的求解方式：

• 在给定的搜索空间（或解空间）里，穷尽所有可能的方案；
• 验证每一种方案是否满足问题所需的条件；
• 最终得到正确解答。

它的本质就是彻底的「暴力搜索」：不放过任何一个可能候选，依次进行计算或验证。通常具有以下特点：

1. 简单易理解：实现原理直接，容易上手。
2. 可能非常耗时：当搜索空间很大时，时间复杂度呈指数级或多项式级的高次幂增长，导致在大规模输入下无法迅速得出结果。
3. 适用中小规模问题或特殊场景：在搜索空间不大的情况下，枚举反而能快速并准确地得到答案。

2. 枚举算法的核心思想

1. 罗列所有可能解
   • 将所有潜在候选（如全排列、组合、子集等）逐个生成；
   • 或在定义的搜索空间中，按某种顺序对每一个「状态」进行遍历。
2. 判断解的可行性或筛选条件
   • 对于枚举到的每个候选解，判断是否满足题目要求，如满足特定约束、能否构成可行解等。
   • 可能需要统计、计算、验证等操作。
3. 记录最优解或全部解
   • 如果问题需要最优解（如最大、最小），则对每个可行解进行比较；
   • 如果问题需要全部解，则将所有满足条件的候选保存起来。

枚举算法的思维很简单：「有多少可能解，就把它们都查看一遍」。它可应用于：

• 小规模排列组合问题；
• 子集搜索，子序列搜索；
• 棋盘/图中所有路径或状态遍历；
• 灰盒测试、暴力破解等场合。

3. 典型案例

3.1 全排列（Permutation）枚举

问题描述

给定一个不含重复数字的数组 nums，要求输出它的所有全排列。 例如：输入 [1, 2, 3]，输出所有 [1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2]、[3, 2, 1]。

思路解析

1. 数据规模：若数组长度为 n，则有 n!（阶乘）种排列方式。
2. 搜索空间：所有可能的元素排布序列。
3. 枚举过程：
   • 可以使用回溯（backtracking）的方式，逐个交换或挑选元素；
   • 每当排列长度达到 n，就输出或记录该排列。

时间复杂度： O(n!)，因为要穷举所有排列。

public class Permutation {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<List<Integer>> result) {
        // 如果 start 已到达数组末尾，则记录当前排列
        if (start == nums.length) {
            List<Integer> onePermutation = new ArrayList<>();
            for (int num : nums) {
                onePermutation.add(num);
            }
            result.add(onePermutation);
            return;
        }
        // 枚举：将每个位置的元素，与 start 位置交换
        for (int i = start; i < nums.length; i++) {
            swap(nums, i, start);
            backtrack(nums, start + 1, result);
            swap(nums, i, start); // 回溯
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

3.2 子集（Subsets）枚举

问题描述

给定一个不含重复数字的数组 nums，返回该数组所有子集（即所有可能的子序列组合，包括空集和自身）。 例如：输入 [1, 2, 3]，输出 [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]。

思路解析

1. 搜索空间：对于每个元素，都有「选」或「不选」两种选择，总共有 2^n 种子集。
2. 枚举过程：
   • 使用回溯或二进制位思想，都可以完成子集的枚举。
   • 回溯时：深度遍历树状结构，每次选择「拿 or 不拿」该元素。

时间复杂度： O((2^n)，每个元素有选或不选两种可能。

public class SubsetEnumeration {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        // 收集当前子集
        result.add(new ArrayList<>(path));
        // 从当前索引开始，逐个决定要不要选
        for (int i = start; i < nums.length; i++) {
            // 做选择：选 nums[i]
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            // 撤销选择
            path.remove(path.size() - 1);
        }
    }
}

3.3 「背包问题」的简单枚举

问题描述

给定一组物品，每件物品有价值与体积限制。背包容量为 C，问如何选取物品使总价值最大？ （这里举最简单的 0-1 背包枚举为例，忽略更高效的动态规划做法。）

思路解析

1. 搜索空间：每件物品只有选或不选两种状态，若有 n 件物品，共有 2n2^n 种组合。
2. 枚举过程：
   • 用回溯或二进制枚举，判断若选某件物品，则体积、价值更新；若超过容量则忽略；
   • 最后选出价值最大的组合。

伪代码思路

function backtrack(index, currentWeight, currentValue):
    if index == n: # 所有物品都决策完
        update maxValue = max(maxValue, currentValue)
        return
    # 不选第 index 件
    backtrack(index + 1, currentWeight, currentValue)
    # 选第 index 件（若能容纳）
    if currentWeight + weight[index] <= C:
        backtrack(index + 1, currentWeight + weight[index], currentValue + value[index])

时间复杂度：O(2^n)，每件物品选或不选。

3.4 字符串匹配的朴素枚举（Brute Force String Matching）

问题描述

在字符串 text 中搜索模式串 pattern，找到 pattern 所有出现的位置。（如 text = "ababcababc"，pattern = "abc"）

思路解析

1. 朴素枚举：
   • 从 text 的每一个可能起始位置 i 出发，对比 pattern 中每一个字符，看是否匹配成功；
   • 若在 i 处能连续匹配全部字符，则记录位置 i。
2. 搜索空间：若 text 长度为 n，pattern 长度为 m，则有 n - m + 1 个起始点要枚举，每个起始点最多比较 m 次。

时间复杂度：最坏 O(n * m)，这是枚举起始位置后逐字比较的耗时。

public class BruteForceStringSearch {
    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            // 检查从 i 开始的 m 个字符是否与 pattern 匹配
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                result.add(i); // 找到一次出现
            }
        }
        return result;
    }
}

4. 枚举算法的优缺点

优点

1. 实现简单：没有复杂的逻辑；思路直观，容易编码。
2. 适用小规模或特定限制的场合：当输入数据规模不大时，枚举往往就能在可接受的时间内求得准确解。
3. 能保证找到正确解：只要搜索空间穷尽所有可能，结果一定正确。

缺点

1. 时间复杂度高：常见是指数级、阶乘级或大多项式级，容易导致无法在大规模数据下跑完。
2. 无法适应大规模问题：当 n 较大时，枚举可能变得不可行。

5. 典型应用与复杂度

应用场景	搜索空间大小	时间复杂度	备注
全排列	n!	O(n!)	n 较小时可行；n 大则极慢
子集、子序列枚举	2^n	O(2^n)	回溯或二进制思路
0-1 背包的朴素解	2^n	O(2^n)	动规可将其降到 O(nC)
字符串朴素匹配	n - m + 1 个起始位置，每次比较至多 mm 次	O(nm)O(nm)	KMP、BM、RK 等算法更高效
解密码/测试漏洞的暴力破解	取决于密码或可用字符长度	通常指数级	实际中常结合彩虹表等技术

总的来说，枚举算法对搜索空间有限的问题非常有效。一旦搜索空间数量级（如 n!、^n 等）变得庞大，往往需要更优化或剪枝策略（如回溯+剪枝、动态规划、贪心、启发式搜索等）来提升效率。

6. 枚举算法的扩展与优化

1. 回溯 + 剪枝
   • 在枚举过程中，一旦发现某个部分解已经不可能得到更优结果或已违反问题约束，立即停止搜索该分支，减小搜索空间。
2. 位运算技巧
   • 对组合、子集等问题，可以用整数的二进制位来表示是否选择某元素，从而简化编码，实现子集或组合枚举。
3. 分治 + 枚举
   • 对一些特别大的搜索空间，可能把问题分成两部分各自枚举，然后再合并。这种「meet in the middle（折半搜索）」能将复杂度从 O(2n)O(2^n) 降到 O(2n/2)O(2^{n/2})，在某些中等规模数据下能极大提升速度。
4. 并行/分布式
   • 如果问题允许并行化，可以把搜索空间拆分给不同机器或线程处理，汇总结果，也是一种「提高枚举算法效率」的思路。