如何高效生成整数数组的不同对半拆分组合？

首先明确核心需求：将数组拆分为两个非空子集对（(S1, S2)），其中S1与S2无交集、并集为原数组，且(S1, S2)和(S2, S1)视为不同组合；同时要避免暴力枚举的低效问题。

以下分两种常见拆分场景给出高效实现思路：

场景1：拆分为长度相等的两个子集（仅数组长度为偶数时可行） #

比如数组长度为2n，拆分为两个长度为n的子集。

核心优化思路 #

1. 排序去重：先对数组排序，回溯时跳过重复元素，避免生成内容完全相同的子集。
2. 回溯剪枝：通过回溯法生成所有唯一的n元素子集，每个子集直接对应一个拆分对(S1, S2)，其中S2为原数组中不在S1的元素。
3. 有序组合处理：若S1≠S2，则同时将(S2, S1)加入结果（因为二者视为不同组合）；若S1=S2（如数组元素全重复），则仅保留一次。

Python 实现代码 #

def generate_equal_splits(arr):
    n = len(arr)
    if n % 2 != 0:
        return []
    target_len = n // 2
    arr.sort()
    result = []
    used = [False] * n

    def backtrack(start, path):
        if len(path) == target_len:
            # 生成S1和对应的S2
            s1 = path.copy()
            s2 = [arr[i] for i in range(n) if not used[i]]
            result.append((s1, s2))
            # 若S1≠S2，加入反向组合
            if s1 != s2:
                result.append((s2, s1))
            return
        for i in range(start, n):
            # 跳过重复元素，避免生成重复子集
            if i > start and arr[i] == arr[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(arr[i])
            backtrack(i+1, path)
            path.pop()
            used[i] = False

    backtrack(0, [])
    # 最终去重，确保无重复组合
    unique_result = []
    seen = set()
    for pair in result:
        key = (tuple(pair[0]), tuple(pair[1]))
        if key not in seen:
            seen.add(key)
            unique_result.append(pair)
    return unique_result

场景2：拆分为任意两个非空子集（不限制长度） #

适用于所有长度≥2的数组，拆分后的两个子集长度可以任意（只要非空）。

核心优化思路 #

1. 排序去重：同样先排序数组，回溯时跳过重复元素，减少无效计算。
2. 回溯生成唯一子集：枚举所有非空真子集，每个子集对应一个拆分对(S1, S2)，其中S2为原数组剩余元素。
3. 结果去重：通过哈希集合过滤内容完全相同的组合。

Python 实现代码 #

def generate_all_splits(arr):
    m = len(arr)
    if m < 2:
        return []
    arr.sort()
    result = []
    used = [False] * m

    def backtrack(start, path):
        if path:
            s2 = [arr[i] for i in range(m) if not used[i]]
            if s2:  # 确保S2非空
                s1 = path.copy()
                result.append((s1, s2))
        for i in range(start, m):
            if i > start and arr[i] == arr[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(arr[i])
            backtrack(i+1, path)
            path.pop()
            used[i] = False

    backtrack(0, [])
    # 去重处理
    unique_result = []
    seen = set()
    for pair in result:
        key = (tuple(pair[0]), tuple(pair[1]))
        if key not in seen:
            seen.add(key)
            unique_result.append(pair)
    return unique_result

特殊需求：子集元素顺序视为组合差异 #

如果要求[2,1]和[1,2]视为不同子集（即基于数组索引的拆分），则无需排序去重，直接通过索引回溯生成所有可能的拆分：

Python 实现代码 #

def generate_ordered_splits(arr):
    m = len(arr)
    if m < 2:
        return []
    result = []
    used = [False] * m

    def backtrack(path):
        if path:
            s2 = [arr[i] for i in range(m) if not used[i]]
            if s2:
                s1 = [arr[i] for i in path]
                result.append((s1, s2))
        # 从下一个索引开始，避免重复排列
        start = path[-1] + 1 if path else 0
        for i in range(start, m):
            if not used[i]:
                used[i] = True
                path.append(i)
                backtrack(path)
                path.pop()
                used[i] = False

    backtrack([])
    return result

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