穷举算法：最基础直观的暴力搜索算法

一、简介

1、简介

穷举算法（Enumeration Algorithm），也被称为暴力搜索算法，是一种在问题域的解空间中对所有可能的解穷举搜索，并根据条件选择最优解的方法的总称。

理论上，穷举法可以解决许多计算领域的问题（只要机器性能足够或者时间开销可承受）。并且在一些较为基本的问题的求解中运用十分广泛，比如求n个数的和。
穷举法可以用于解决一些规模较小的问题，因为其时间规模在可承受范围内。
对于某方面的问题（比如排序、查找、串匹配），可以基于穷举法设计出一些优化算法，这些优化算法是可用并且具有实用价值的，比如说KMP算法就是基于穷举法优化的串匹配算法。
穷举可以作为某类问题的时间性能下界，来衡量同样问题其他算法是否具有更高效率。

2、缺点

（1）时间复杂度极高，效率低下
穷举的时间复杂度通常为O(n^k)（n 为单个变量的解空间大小，k 为变量个数），随着解空间增大，执行时间呈指数级增长。例如：3 位数字密码（10^3=1000 次遍历），10 位数字密码（10^10=100 亿次遍历），几乎无法完成。

（2）不适用于大规模解空间问题
对于海量数据、长密码、复杂组合问题，穷举算法完全无法满足需求，必须依赖更高效的算法（如动态规划、哈希表、二分查找等）。

3、优化技巧

（1）优先缩小解空间范围（核心优化）
这是穷举优化的关键，通过业务逻辑、数学推导，尽可能减少候选解的数量。例如：百钱买百鸡中，公鸡 x 的范围从0~100 缩小到 0~20，大幅减少遍历次数。

（2）采用“剪枝”技巧，提前跳出无效循环
对解空间穷举搜索时，如果有一些状态节点可以根据问题提供的信息明确地被判定为不可能演化出最优解，也就是说，从此节点开始遍历得到的子树，可能存在正确的解，但是肯定不是最优解，就可以跳过此状态节点的遍历，这将极大地提高算法的执行效率，这就是剪枝策略，应用剪枝策略的难点在于如何找到一个评价方法（估值函数）对状态节点进行评估。

（3）利用数学规律优化遍历策略
借助数学规律（如因数的对称性、质数的性质），减少遍历次数。例如：求因数时遍历到Math.sqrt(num)，而非num。

（4）先评估解空间大小，再决定是否使用穷举
使用前先计算解空间的大小，若解空间过大（如超过10^6次遍历），直接放弃穷举，选择更高效的算法。例如：10 位数字密码的解空间为 10^10，穷举不可行，应选择密码破解专用算法。

（5）避免重复遍历，优化组合策略
对于组合问题（如两数之和），采用i < j等策略避免重复遍历同一组合，减少无效验证。

（6）注意边界条件的处理
划定解空间时，注意边界值（如质数的边界是大于 1，因数的边界是 1 和自身），避免遗漏边界解或出现数组越界、整数溢出等问题。

（7）找到目标解后立即终止遍历（若无需所有解）
若问题只需找到一个有效解（如密码破解），找到后立即使用break（或return）终止遍历，无需继续遍历剩余候选解。

（8）大规模解空间问题，禁止使用纯穷举
对于大规模解空间问题，可结合其他算法优化（如穷举 + 剪枝、穷举 + 动态规划），或直接选择更高效的算法，切勿使用纯穷举。

二、经典案例

1、百钱买百鸡（经典多变量穷举）

公鸡 5 文钱 1 只，母鸡 3 文钱 1 只，小鸡 3 只 1 文钱，用 100 文钱买 100 只鸡，求公鸡、母鸡、小鸡各有多少只。

这是多变量穷举，通过嵌套循环遍历两个变量（x、y），第三个变量（z）通过逻辑推导得出，减少了一层循环，优化了解空间。
关键是提前缩小变量的遍历范围（x≤20、y≤33），避免无意义的遍历（比如 x=21 时，仅公鸡就超过 100 文钱）。

/** * 穷举示例1：百钱买百鸡 */publicclassEnumerationExample1{publicstaticvoidmain(String[]args){System.out.println("百钱买百鸡的有效解：");// 划定解空间（减少无效遍历，优化解空间范围）// 公鸡x：最多买 100/5=20 只for(intx=0;x<=20;x++){// 母鸡y：最多买 100/3≈33 只for(inty=0;y<=33;y++){// 小鸡z：总数100，所以z=100-x-y，且必须是3的倍数（因为3只1文钱）intz=100-x-y;// 验证条件1：总钱数=100；验证条件2：小鸡数量是3的倍数if(z%3==0&&(5*x+3*y+z/3==100)){System.out.printf("公鸡：%d 只，母鸡：%d 只，小鸡：%d 只%n",x,y,z);}}}}}// 结果：百钱买百鸡的有效解： 公鸡：0只，母鸡：25只，小鸡：75只 公鸡：4只，母鸡：18只，小鸡：78只 公鸡：8只，母鸡：11只，小鸡：81只 公鸡：12只，母鸡：4只，小鸡：84只

2、查找指定范围内的质数（单变量穷举 + 验证优化）

找出 100 以内的所有质数（质数：大于 1，且只能被 1 和自身整除的正整数）。

这是单变量穷举，核心优化点是遍历到Math.sqrt(num)而非num-1，大幅减少了遍历次数（比如 num=100，只需遍历到 10，而非 99）。
引入break语句提前跳出无效循环，是穷举中常用的 “剪枝” 技巧，减少资源消耗。

/** * 穷举示例2：查找100以内的所有质数 */publicclassEnumerationExample2{publicstaticvoidmain(String[]args){System.out.println("100以内的所有质数：");// 划定解空间：2~100（质数大于1）for(intnum=2;num<=100;num++){booleanisPrime=true;// 标记是否为质数// 遍历策略+验证优化：只需遍历到√num（大于√num的因数必然和小于√num的因数成对出现）for(inti=2;i<=Math.sqrt(num);i++){if(num%i==0){// 验证条件：能被其他数整除，不是质数isPrime=false;break;// 提前跳出循环，减少无效遍历（剪枝思想）}}// 收集有效解if(isPrime){System.out.print(num+" ");}}}}// 结果：100以内的所有质数：2357111317192329313741434753596167717379838997

3、简单数字密码破解（固定长度穷举）

破解一个 3 位数字密码（密码范围 000~999），已知目标密码为 668，通过穷举找到该密码并输出。

这是固定范围的单值穷举，解空间大小固定（1000 个候选解），效率极高。
采用%03d格式化输出，保证密码的 3 位格式（比如 0 会输出为 000），贴合实际密码场景。
找到目标后立即break，避免不必要的后续遍历，优化执行效率。

/** * 穷举示例3：3位数字密码破解 */publicclassEnumerationExample3{publicstaticvoidmain(String[]args){finalintTARGET_PASSWORD=668;// 目标密码System.out.println("开始穷举破解3位数字密码...");// 划定解空间：0~999（3位数字密码的所有可能）for(intpassword=0;password<=999;password++){// 验证条件：当前候选密码等于目标密码if(password==TARGET_PASSWORD){System.out.printf("密码破解成功！目标密码是：%03d%n",password);// %03d 保证输出3位，补前导0break;// 找到后立即退出，无需继续遍历}}}}

4、数组中两数之和等于目标值（两两组合穷举）

给定一个整数数组，穷举所有两两组合，找到和等于目标值的所有索引对（不重复）。

这是组合穷举，通过嵌套循环遍历数组的所有两两组合，采用i < j的策略避免重复索引对（比如 (0,1) 和 (1,0) 视为同一对，只保留前者）。
适用于小规模数组，若数组长度超过 1000，嵌套循环的时间复杂度（O (n²)）会导致效率急剧下降。

importjava.util.ArrayList;importjava.util.List;/** * 穷举示例4：数组中两数之和等于目标值 */publicclassEnumerationExample4{publicstaticvoidmain(String[]args){int[]nums={2,7,11,15,3,6};inttarget=9;List<String>result=newArrayList<>();// 存储结果索引对// 划定解空间：数组中所有两两组合（i < j 避免重复索引对）for(inti=0;i<nums.length;i++){for(intj=i+1;j<nums.length;j++){// 验证条件：两数之和等于目标值if(nums[i]+nums[j]==target){result.add(String.format("(%d, %d)",i,j));}}}// 输出结果if(result.isEmpty()){System.out.println("未找到和等于目标值的两数组合");}else{System.out.printf("和等于%d的索引对有：%s%n",target,String.join("，",result));}}}// 结果：和等于9的索引对有：(0,1)，(4,5)

5、优惠券最优组合分配（分配问题・金额匹配）

电商下单场景：用户订单金额100 元，账户中有多张不同面额的无门槛优惠券，最多选 3 张使用，要求优惠券总抵扣金额≤订单金额，且抵扣金额最大（核心是有限张数的优惠券分配，实现最优抵扣）。

importjava.util.ArrayList;importjava.util.List;/** * 电商优惠券最优组合分配（分配问题） */publicclassBusinessModel1_CouponAssign{publicstaticvoidmain(String[]args){intorderAmount=100;// 订单金额int[]coupons={10,20,30,15,25};// 优惠券面额列表intmaxSelect=3;// 最多选3张intmaxDeduct=0;// 最大抵扣金额List<List<Integer>>bestCombination=newArrayList<>();// 最优组合（可能多个）// 1. 穷举1张优惠券的情况for(inti=0;i<coupons.length;i++){intdeduct=coupons[i];if(deduct<=orderAmount&&deduct>maxDeduct){maxDeduct=deduct;bestCombination.clear();bestCombination.add(List.of(coupons[i]));}elseif(deduct==maxDeduct){bestCombination.add(List.of(coupons[i]));}}// 2. 穷举2张优惠券的情况（i<j 避免重复）for(inti=0;i<coupons.length;i++){for(intj=i+1;j<coupons.length;j++){intdeduct=coupons[i]+coupons[j];if(deduct<=orderAmount){updateBestCombination(deduct,maxDeduct,List.of(coupons[i],coupons[j]),bestCombination);maxDeduct=Math.max(maxDeduct,deduct);}}}// 3. 穷举3张优惠券的情况（i<j<k 避免重复）for(inti=0;i<coupons.length;i++){for(intj=i+1;j<coupons.length;j++){for(intk=j+1;k<coupons.length;k++){intdeduct=coupons[i]+coupons[j]+coupons[k];if(deduct<=orderAmount){updateBestCombination(deduct,maxDeduct,List.of(coupons[i],coupons[j],coupons[k]),bestCombination);maxDeduct=Math.max(maxDeduct,deduct);}}}}// 输出结果System.out.printf("订单金额：%d元，最多选%d张优惠券%n",orderAmount,maxSelect);System.out.printf("最大抵扣金额：%d元%n",maxDeduct);System.out.println("最优优惠券组合："+bestCombination);}// 辅助方法：更新最优组合privatestaticvoidupdateBestCombination(intcurrentDeduct,intmaxDeduct,List<Integer>combination,List<List<Integer>>bestCombination){if(currentDeduct>maxDeduct){bestCombination.clear();bestCombination.add(newArrayList<>(combination));}elseif(currentDeduct==maxDeduct){bestCombination.add(newArrayList<>(combination));}}}// 结果：订单金额：100元，最多选3张优惠券 最大抵扣金额：75元 最优优惠券组合：[[20,30,25]]

6、商品库存组合计数（计数问题・空间匹配）

线下门店货架场景：某货架的最大摆放空间为 8 个单位，现有 4 类商品，每类商品占不同的摆放空间，每类商品仅能摆放 1 件，求能摆满 / 摆放的有效商品组合数（核心是统计符合空间约束的商品组合数量）。

importjava.util.ArrayList;importjava.util.List;/** * 门店商品库存组合计数（计数问题） */publicclassBusinessModel2_GoodsCount{publicstaticvoidmain(String[]args){int[]goodsSpace={2,3,1,4};// 商品1~4的占用空间intmaxSpace=8;// 货架最大摆放空间intvalidCount=0;// 有效组合数List<List<Integer>>validCombinations=newArrayList<>();// 所有有效组合// 穷举所有非空组合：用位运算（4位二进制，0=不选，1=选，0001~1111）intn=goodsSpace.length;for(intmask=1;mask<(1<<n);mask++){List<Integer>combination=newArrayList<>();inttotalSpace=0;// 遍历每一位，判断是否选中该商品for(inti=0;i<n;i++){if((mask&(1<<i))!=0){combination.add(goodsSpace[i]);totalSpace+=goodsSpace[i];}}// 验证约束条件：总空间≤货架最大空间if(totalSpace<=maxSpace){validCount++;validCombinations.add(combination);}}// 输出结果System.out.printf("货架最大空间：%d个单位，商品占用空间：%s%n",maxSpace,List.of(2,3,1,4));System.out.printf("有效商品组合数：%d个%n",validCount);System.out.println("所有有效组合（占用空间）："+validCombinations);}}