固定子集大小的多集合全组合生成实现及问题解决

问题本质拆解 #

你要解决的其实是全集的指定大小无序分组生成：给定全集和一组目标子集大小，生成所有满足大小要求的元素划分，且子集内部无序、同大小的子集顺序不视为新组合。之前的问题要么是只做了单次交换导致漏组合，要么是递归时没加约束导致重复。

核心解决方案思路 #

通过约束元素选择顺序避免重复，同时遍历所有可能的元素分配：

1. 先对全集排序，为后续去重判断提供统一基准
2. 递归构建每个子集：
   • 生成当前子集时，仅从「未被选中且索引不小于当前起始位置」的元素中选择，避免生成顺序不同但元素相同的子集
   • 遇到重复元素直接跳过，进一步减少重复分组
   • 当前子集达到目标大小后，递归构建下一个子集，直到所有子集完成

TypeScript 实现代码 #

function generateAllPartitions<T>(fullSet: T[], targetSizes: number[]): T[][][] {
    // 排序全集，为去重和约束选择顺序做准备
    const sortedElements = [...fullSet].sort();
    const result: T[][][] = [];

    // 递归回溯：已构建的子集、剩余元素、当前要构建的子集索引
    const backtrack = (currentPartitions: T[][], remaining: T[], sizeIndex: number) => {
        // 所有子集构建完成，存入结果
        if (sizeIndex === targetSizes.length) {
            result.push([...currentPartitions.map(p => [...p].sort())]);
            return;
        }

        const targetSize = targetSizes[sizeIndex];
        // 剩余元素刚好匹配当前子集大小，直接使用
        if (remaining.length === targetSize) {
            backtrack([...currentPartitions, remaining], [], sizeIndex + 1);
            return;
        }

        // 生成当前子集的所有合法组合，通过起始索引避免重复
        const buildSubset = (startIdx: number, currentSubset: T[]) => {
            if (currentSubset.length === targetSize) {
                // 计算剩余元素：移除当前子集已选元素
                const newRemaining = remaining.filter(item => !currentSubset.includes(item));
                backtrack([...currentPartitions, currentSubset], newRemaining, sizeIndex + 1);
                return;
            }

            // 从startIdx开始遍历，避免生成顺序不同的重复子集
            for (let i = startIdx; i < remaining.length; i++) {
                // 跳过重复元素，避免相同元素的重复组合
                if (i > startIdx && remaining[i] === remaining[i-1]) continue;
                buildSubset(i + 1, [...currentSubset, remaining[i]]);
            }
        };

        buildSubset(0, []);
    };

    backtrack([], sortedElements, 0);
    return result;
}

// 示例测试
const fullSet = [1,2,3,4,5,6,7,8,9,10];
const targetSizes = [4,4,2];
const allPartitions = generateAllPartitions(fullSet, targetSizes);

// 验证是否包含你提到的缺失组合
const missingExample = [[1,2,3,6], [4,5,7,8], [9,10]];
console.log(allPartitions.some(partition => 
    partition.every(subset => 
        JSON.stringify(subset.sort()) === JSON.stringify(missingExample.find(s => s.length === subset.length)?.sort())
    )
)); // 输出true，说明已包含目标组合

关键细节说明 #

• 排序约束：对全集和每个子集排序，确保相同元素组合的表示一致，方便后续校验和去重
• 递归索引控制：生成子集时从指定起始索引开始遍历，彻底避免「元素相同但顺序不同」的重复子集
• 重复元素跳过：如果全集有重复元素，跳过相邻重复项可以直接减少无效的重复分组

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