如何提升Python中itertools.combinations运行速度？CodeWars任务优化

问题根源 #

你当前的实现通过生成所有非空子集的组合来计数，时间复杂度是O(2ⁿ)（n为去重后的元素数量）。当n较大时，生成并遍历所有组合会消耗大量的时间和内存，这是速度慢的核心原因。

数学优化思路 #

去重后的集合有n个唯一元素，每个元素只有两种选择：出现在子集中或不出现在子集中，因此总子集数为2ⁿ。题目要求返回不含重复元素的非空子集数量，最终结果直接用2ⁿ - 1计算即可（减去空集）。

优化后的代码 #

def est_subsets(a):
    unique_count = len(set(a))
    return (1 << unique_count) - 1  # 位运算计算2的n次方，效率高于pow

如果觉得位运算不够直观，也可以用更易懂的写法：

def est_subsets(a):
    unique_count = len(set(a))
    return pow(2, unique_count) - 1

优化效果说明 #

• 时间复杂度直接从O(2ⁿ)降到O(1)，只需要统计去重后的元素数量，再通过数学公式得出结果，完全不需要生成任何子集组合。
• 位运算1 << unique_count在Python中计算2的整数幂效率极高，比调用pow函数的性能略优。

验证示例 #

比如输入a = ['a','b','b','c']，去重后有3个元素，结果应为2³-1=7，对应子集：{'a'}, {'b'}, {'c'}, {'a','b'}, {'a','c'}, {'b','c'}, {'a','b','c'}，和原代码结果完全一致，但计算速度提升几个数量级。

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