将整数表示为不同k次幂之和的算法优化求助

原代码的核心问题是生成所有可能的子集，当候选整数数量较多时（如solutions(1000,2)时候选数有31个），子集总数达到2^31，直接导致内存溢出。以下是针对性的优化方案：

核心思路 #

采用回溯+剪枝的方式，只遍历有效的组合路径：

• 逐个考虑每个候选整数，选择“包含”或“不包含”它
• 若当前总和已超过目标n，立即终止当前分支（剪枝）
• 若当前总和等于n，记录该组合
• 按从小到大的顺序遍历，利用有序性提前终止无效分支（后续数的k次幂更大，总和必然超n）

优化后的代码 #

def possible_powers(n, k):
    power_pairs = []
    num = 1
    while True:
        power_val = num ** k
        if power_val > n:
            break
        # 存储整数及其对应的k次幂，避免重复计算
        power_pairs.append((num, power_val))
        num += 1
    return power_pairs

def solutions(n, k):
    power_pairs = possible_powers(n, k)
    result = []
    
    def backtrack(start_idx, current_sum, current_comb):
        # 找到符合条件的组合，加入结果
        if current_sum == n:
            result.append(current_comb.copy())
            return
        # 总和超过n，剪枝，终止当前分支
        if current_sum > n:
            return
        
        for i in range(start_idx, len(power_pairs)):
            num, val = power_pairs[i]
            # 若加入当前幂值后总和超n，后续数的幂值更大，直接终止循环
            if current_sum + val > n:
                break
            # 选择当前数
            current_comb.append(num)
            # 递归处理下一个数（避免重复组合，从i+1开始）
            backtrack(i + 1, current_sum + val, current_comb)
            # 回溯，撤销选择
            current_comb.pop()
    
    backtrack(0, 0, [])
    # 保持与原代码一致的返回格式
    return [(k, comb) for comb in result]

优化点说明 #

1. 预计算幂值：possible_powers返回整数与对应k次幂的元组，避免递归过程中重复计算num**k，提升效率。
2. 回溯剪枝：仅遍历有效路径，不会生成所有子集，内存占用仅取决于当前递归深度和符合条件的组合数量，彻底解决内存溢出问题。
3. 有序剪枝：按从小到大遍历候选数，当current_sum + val > n时直接break，跳过所有后续更大的数，大幅减少无效遍历次数。

测试验证 #

以n=100, k=2为例，优化后的代码会返回3种组合：

[(2, [10]), (2, [6, 8]), (2, [1, 2, 3, 4, 5, 7])]

与原代码结果一致，但内存占用和执行效率提升几个数量级。

内容的提问来源于stack exchange，提问作者Reggie Floarde