1. 项目概述从“四平方和”看蓝桥杯的DFS考察逻辑看到“四平方和”这个题目再配上“DFS”这个标签很多正在备战蓝桥杯的同学可能会心头一紧。这题在蓝桥杯的题库里尤其是涉及搜索算法的部分算是一个经典的中等难度题目了。它不像一些纯暴力枚举题那样简单直接也不像复杂的图论搜索那样让人望而生畏它恰恰卡在一个非常巧妙的位置考察你是否真正理解了深度优先搜索DFS在解决组合问题时的“剪枝”艺术以及如何将数学特性转化为程序优化的直觉。简单来说题目要求对于一个给定的正整数n找到四个非负整数a, b, c, d满足a² b² c² d² n。并且如果有多组解需要输出字典序最小的那一组。这里的字典序通常定义为(a, b, c, d)作为一个元组按顺序比较大小。为什么DFS是解决这道题的一个好方法因为本质上我们是在一个四层的决策树上进行搜索每一层决定一个数的值。最笨的方法就是四重循环从0遍历到sqrt(n)。但蓝桥杯的题目往往对时间和空间有严格限制直接四重循环在n较大时必然超时。这就需要DFS结合剪枝策略提前砍掉大量不可能的分支从而在限定时间内找到答案。这道题就是一个绝佳的练习场让你不是仅仅会写DFS的框架而是学会如何让DFS变得“聪明”起来。接下来我会拆解这道题的几种DFS思路从最基础的到逐步优化的并分享我在调试这类搜索题时的一些核心心法和避坑技巧。2. 核心思路解析与DFS方案选型面对“四平方和”我们首先要摒弃暴力四重循环的想法虽然它逻辑正确但竞赛中几乎不可能通过。DFS为我们提供了结构化的搜索路径关键在于如何设计搜索状态和剪枝条件。2.1 搜索状态的设计一个直观的DFS状态设计是dfs(idx, sum, path)。idx: 当前正在决定第几个数0, 1, 2, 3分别代表a, b, c, d。sum: 当前已经选出的数的平方和。path: 一个列表记录当前已经选择的[a, b, c, ...]。初始状态为dfs(0, 0, [])表示从第0个数开始当前和为0路径为空。递归边界条件是当idx 4时检查sum n如果相等则找到一个合法解。2.2 搜索顺序与字典序处理题目要求输出字典序最小的解。DFS如何保证这一点答案在于搜索顺序本身。如果我们让每一层每个位置的数字都从0开始从小到大进行尝试那么第一个被完整搜索到并满足条件的四元组(a, b, c, d)自然就是字典序最小的。因为DFS是深度优先它会固定前几个数尽可能深地搜索后续数字。当a最小且存在解时它一定会被最先找到。这是一个非常重要的特性利用好它可以省去后续比较字典序的麻烦。2.3 关键优化点剪枝策略这是本题的核心价值所在。没有剪枝的DFS和暴力循环区别不大。主要剪枝策略有上限剪枝对于当前要选择的数字x其最大值不能超过sqrt(remaining_sum)其中remaining_sum n - sum。因为x²不能大于剩余所需的和。下限剪枝可行性剪枝即使当前x取最大值如果剩下的位置4 - idx - 1个都取可能的最小值0其平方和也可能无法达到remaining_sum。但更常用的是一种“平衡性”思想。非递增顺序剪枝重要为了进一步减少搜索量并利用字典序的特性我们可以强制要求a b c d。这并不会漏掉解因为对于任何一组解(a,b,c,d)我们都可以将其排序后得到一个满足非递增顺序的解而这个解对应的原始解经过排序后如果从大到小赋值并调整搜索顺序依然能找到字典序最小的那个这里需要仔细理解通常我们直接采用非递减顺序a b c d来避免重复搜索但要注意和字典序的配合。提前终止一旦找到第一个解由于我们的搜索顺序保证了字典序最小因此可以立即记录答案并终止所有递归。在实际编码中策略3顺序剪枝和策略1上限剪枝结合使用效果最为显著。策略2通常用于更复杂的优化在本题中通过策略1和3已经能获得很好的效果。注意强制顺序剪枝时要清楚它如何与“字典序最小”互动。如果我们要求a b c d并且按从小到大的顺序搜索每个数那么找到的第一个解就是满足此顺序下的字典序最小解。而题目要求的全局字典序最小解一定可以通过重排满足某种顺序所以这个方法是正确的但理解其等价性很重要。3. DFS算法实现与逐行详解接下来我们实现一个带有剪枝的DFS解法。这里我给出一个Python版本并详细解释每一部分的作用和原理。import math def four_square_sum(n): 使用DFS搜索四平方和返回字典序最小的解 [a, b, c, d]。 result [] # 用于存储找到的第一个解即字典序最小解 max_val int(math.sqrt(n)) 1 # 每个数的最大可能值 def dfs(idx, current_sum, path): idx: 当前要确定第几个数 (0-based) current_sum: 当前已选数字的平方和 path: 当前已选的数字列表 nonlocal result # 剪枝1: 如果已经找到解立即终止所有搜索 if result: return # 递归边界已经选了4个数 if idx 4: if current_sum n: result.extend(path) # 找到解复制到result return # 剪枝2: 计算剩余所需的和 remaining n - current_sum if remaining 0: # 当前和已经超过n不可能剪枝 return # 确定当前层数字的搜索范围 # 起始值为了保持非递减顺序以去重和维持字典序当前数不能小于前一个数如果存在 start_val path[-1] if path else 0 # 结束值当前数的平方不能超过剩余和同时不能超过全局最大值 end_val min(int(math.sqrt(remaining)), max_val) # 遍历当前所有可能的选择 for x in range(start_val, end_val 1): # 生成新的路径和新的和 new_path path [x] new_sum current_sum x * x # 剪枝3可行性剪枝的强化版预测未来最小值 # 如果剩下的位置都取当前能取的最小值即start_val因为非递减其平方和可能已经超过剩余所需 # 更实用的剪枝是如果当前x过大导致即使后面都取最小的x平方和也会超过remaining则可以剪枝。 # 这里我们采用一个简单的剩余位置最小平方和判断 # 剩余位置数 4 - idx - 1 # 每个位置至少取 start_val (实际上为了更紧可以认为至少取x因为非递减) # 但这个计算略复杂对于本题先使用主要剪枝1和2。 # 关键剪枝4剩余和是否可能用剩余的数字填满 # 假设后面每个数都取最大值end_val其平方和可能仍小于remaining吗 # 更常见的写法是判断如果 current_sum x*x (4-idx-1)*(end_val**2) n则即使后面全取最大也可能不够剪枝。 # 但这里我们选择另一种如果 current_sum x*x n则剪枝已由前面的remaining0覆盖。 # 一个更强的剪枝是remaining 必须大于等于 (4-idx-1) * (start_val**2)因为后面每个数至少是start_val。 # 我们实现这个 min_future_sum (4 - idx - 1) * (x * x) # 后面每个数至少和当前x一样大非递减 if new_sum min_future_sum n: # 即使后面都取和当前x一样大总和也会超过n说明当前x太大了可以break而不是continue # 因为x是递增的后面的x只会更大所以直接跳出循环 break # 继续向下搜索 dfs(idx 1, new_sum, new_path) # 如果已经找到解快速返回 if result: return # 开始DFS搜索 dfs(0, 0, []) return result # 测试用例 if __name__ __main__: n 5 # 5 1² 1² 1² 2² print(four_square_sum(n)) # 预期输出 [0, 0, 1, 2] 注意字典序最小0比1小。 # 实际上5 0² 0² 1² 2² 是字典序最小的。 # 输出应为 [0, 0, 1, 2] n2 12 # 12 0² 2² 2² 2² print(four_square_sum(n2)) # 预期输出 [0, 2, 2, 2]3.1 代码关键点解读max_val的计算int(math.sqrt(n)) 1因为任何一个数的平方如果等于n它最大也就是sqrt(n)加1是为了让range能够包含边界值。start_val的确定path[-1] if path else 0。这是实现非递减顺序的关键。当前选择的数x必须不小于前一个数这避免了像(1,0,0,0)和(0,1,0,0)这种实质相同但顺序不同的解被重复搜索极大减少了状态空间。同时它也暗含了字典序的推进。end_val的确定min(int(math.sqrt(remaining)), max_val)。这是上限剪枝。当前数x最大不能超过sqrt(remaining)因为x²不能大于剩余所需的和。同时也不能超过全局最大可能值max_val。强化剪枝min_future_sum这是代码中最精妙的部分之一。min_future_sum (4 - idx - 1) * (x * x)。它估算的是在当前位置选择了x之后剩下的所有位置即使每个位置都只取和当前x一样大的值这是非递减顺序下的最小值估计所得到的最小未来平方和。如果当前和 最小未来平方和 n那么说明即使后面都取可能的最小值总和也已经超过了n当前x的选择必然无解。而且由于x在循环中是递增的一旦这个条件触发后面的x只会更大条件会更不满足所以可以直接break跳出循环而不是continue。这是一个非常强有力的剪枝。结果存储与提前返回使用nonlocal result在嵌套函数中修改外部变量。一旦result被赋值意味着找到了第一个解字典序最小后续的递归调用通过if result: return检查实现全局快速终止节省不必要的计算。3.2 算法复杂度分析最坏情况下理论上我们仍然需要遍历所有可能的四元组数量级是O((sqrt(n))^4)即O(n²)。但通过上述剪枝顺序剪枝将组合数转化为组合数减少了重复。上限剪枝在每一层都大幅减少了循环次数。强化剪枝min_future_sum能在深层递归中提前截断大量分支。 实测表明对于蓝桥杯评测系统常见的n的范围比如n 5*10^6这个DFS算法可以在毫秒级内完成。4. 调试技巧与常见“坑点”实录即便思路清晰实现DFS时也容易掉进一些坑里。下面是我在多次练习和教学中总结出的高频问题。4.1 字典序的误解问题有同学认为要输出字典序最小应该在找到所有解后再用一个排序函数去比较。这种做法不仅效率低下而且容易写错比较逻辑。解决正如之前强调的利用DFS的搜索顺序来保证。让每个数字从小到大尝试并且一旦找到完整的四元组就立即返回这个解就是字典序最小的。这是DFS解决这类“最小字典序”问题的标准且高效的方法。务必在理解搜索树的基础上内化这个观念。4.2 剪枝条件写反或过松问题1上限剪枝end_val计算错误。错误写法end_val int(math.sqrt(n))。这忽略了已经累加的和current_sum导致搜索范围过大。解决必须基于剩余和remaining来计算即int(math.sqrt(remaining))。问题2min_future_sum剪枝条件判断错误。错误写法if new_sum min_future_sum n: break。这完全剪反了它把有可能成功的分支剪掉了而该剪的没剪。解决正确逻辑是如果即使未来取最小可能值总和也超过n则当前分支无望应剪枝。所以条件是而非。同时min_future_sum的估算要合理这里用(剩余位置数) * (当前x的平方)是一个较紧且安全的估计。4.3 递归深度与性能问题n很大时递归调用深度为4这没有问题。但如果不加剪枝递归树的分支会爆炸导致栈溢出或超时。解决剪枝是唯一途径。在编写DFS时要养成“先写剪枝条件”的习惯。每写一层递归立刻思考这一层的取值范围能缩小吗基于当前状态能提前判断后续无解吗min_future_sum这类剪枝需要多加练习才能灵活运用。4.4 输出格式与数据类型问题蓝桥杯的评测机通常要求严格按格式输出。本题可能要求输出四个空格分隔的数。如果你用列表形式输出[0, 0, 1, 2]可能会被判为格式错误。解决仔细阅读题目输出要求。通常的写法是ans four_square_sum(n) print( .join(map(str, ans)))4.5 边界条件n0 和 大数nn0唯一解是(0,0,0,0)。我们的算法中max_val int(math.sqrt(0)) 1 1start_val0,end_valmin(0, 1)0。DFS会尝试a0然后b,c,d也都只能从0开始最终找到[0,0,0,0]正确。大数n重点测试n接近5*10^6的情况。可以在本地用时间测试。确保剪枝有效不会超时。一个技巧是可以尝试让a, b, c, d非递减的剪枝有时比非递增更有效因为数字从小开始增长更容易触发min_future_sum的剪枝。5. 对比其他解法与DFS的适用场景虽然DFS是本题的一种优美解法但并不是唯一解。了解其他解法有助于我们更全面地把握问题。5.1 哈希表空间换时间法一种更快的算法是使用哈希表字典。思路是先用两重循环枚举a和b计算t a*a b*b并将(t, a)存储到字典中以t为键a为值存储最小的a以保证字典序。然后再用两重循环枚举c和d计算remain n - c*c - d*d检查remain是否在字典中。如果在且对应的a满足a c为了配合非递减顺序和字典序则(a, b, c, d)就是一个解由于我们按顺序枚举找到的第一个就是字典序最小解。这种方法的时间复杂度约为O(n)因为两重循环到sqrt(n)但需要O(n)的额外空间。在蓝桥杯环境下如果n很大例如上亿可能会超出内存限制。但对于本题常见范围它通常比DFS更快。def four_square_sum_hash(n): from collections import defaultdict hash_map {} max_val int(math.sqrt(n)) 1 # 先存储所有 a² b² 的可能性 for a in range(max_val): for b in range(a, max_val): # b从a开始保证非递减 t a*a b*b if t not in hash_map: # 只存储最先出现的即a最小的 hash_map[t] a # 然后查找 c² d² for c in range(max_val): for d in range(c, max_val): remain n - c*c - d*d if remain in hash_map: a hash_map[remain] b int(math.sqrt(remain - a*a)) # 根据a和remain反推b # 需要验证 b a 且 a² b² remain if a c and a*a b*b remain: # 验证解的有效性并维持顺序 return [a, b, c, d] return []5.2 DFS与哈希法的选择DFS优势在于无需额外大数组空间复杂度低递归深度为常数代码结构清晰体现了“搜索与剪枝”的算法思想。在面试或初学算法时DFS是更受青睐的解答因为它考察了算法设计能力。哈希法优势在于速度极快是典型的“空间换时间”。在竞赛中如果内存允许哈希法通常是首选因为它更稳定不易被极端数据卡住。对于蓝桥杯练习我强烈建议先掌握DFS解法。因为它能锻炼你设计搜索状态、剪枝优化的核心能力这是解决更复杂搜索题的基础。哈希法更像一个针对此题的特殊技巧。6. 举一反三DFS剪枝的通用心法通过“四平方和”我们可以提炼出DFS剪枝的几种通用策略这些策略在蓝桥杯乃至其他算法竞赛的搜索题中屡试不爽优化搜索顺序优先尝试分支少的选择或者更容易达到目标的选择。本题中“从小到大”枚举既保证了字典序也使得min_future_sum剪枝更有效。排除等效冗余通过规定顺序如非递减来避免搜索本质相同的状态。可行性剪枝在搜索过程中提前判断当前状态是否可能扩展到最终解。min_future_sum n就是典型的可行性剪枝。最优性剪枝对于求最优解如最小步数的问题如果当前代价已经超过已知最优解则剪枝。本题是求可行解所以未使用。记忆化搜索如果搜索过程中会重复到达相同的子状态可以用缓存Memoization存储结果避免重复计算。本题由于状态简单且深度浅未使用。当你拿到一个新的搜索题可以按照这个清单来思考状态如何表示参数搜索顺序如何安排影响字典序和剪枝效率有哪些明显的不可行情况可以提前判断上下界有哪些状态是重复的可以避免顺序规定能否预测未来至少/至多需要多少代价可行性/最优性剪枝把这些想清楚了代码实现就是水到渠成的事情。四平方和这道题就像一把钥匙帮你打开了DFS优化的大门。以后再遇到“凑数字”、“分组”、“排列组合”类的问题你就会有意识地去设计剪枝而不是写一个赤裸裸的暴力搜索然后祈祷数据量小了。