如何用递归实现数组连续分割的全组合生成器？

核心思路 #

每次从数组开头切出一段（长度从1到剩余数组总长度），递归处理剩下的子数组，再把当前片段和递归得到的所有分割结果拼接起来；当数组被切完（空数组）时，触发终止条件。

实现代码 #

def split_array(arr):
    if not arr:
        yield []
        return
    # 遍历所有可能的开头片段长度
    for i in range(1, len(arr) + 1):
        current_segment = arr[:i]
        # 递归处理剩余子数组，拼接结果
        for rest_segments in split_array(arr[i:]):
            yield [current_segment] + rest_segments

测试示例 #

调用方式：

for combo in split_array([1,2,3,4]):
    print(combo)

输出的全部8种组合：

[[1], [2], [3], [4]]
[[1], [2], [3,4]]
[[1], [2,3], [4]]
[[1], [2,3,4]]
[[1,2], [3], [4]]
[[1,2], [3,4]]
[[1,2,3], [4]]
[[1,2,3,4]]

递归切片逻辑说明 #

• arr[:i]：取数组前i个元素作为当前分割片段，i从1开始保证至少切出一个元素。
• split_array(arr[i:])：将数组从第i位开始的剩余部分传入递归函数，继续生成该子数组的所有分割方式。
• 终止条件if not arr：当剩余子数组为空时，返回包含空列表的生成器，此时[current_segment] + rest_segments就只剩当前片段，完成最后一次分割。

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