如何找出数组中席位总和超30的无重复政党组合？

核心思路 #

要找出不重复的政党组合且席位总和超30，关键是生成所有非空的无序子集（避免party1+party2和party2+party1这类重复组合），再筛选出总和符合阈值的结果。

实现代码（基础循环版） #

let testData = {
    "party1":19,
    "party2":29,
    "party3":10,
};
let testArr = Object.entries(testData);
const majorityThreshold = 30;
const validCombinations = [];

// 处理单个政党的情况
testArr.forEach(([party, seats]) => {
    if (seats > majorityThreshold) {
        validCombinations.push({
            parties: [party],
            totalSeats: seats
        });
    }
});

// 处理2个及以上政党的组合，通过索引递增避免重复
const partyCount = testArr.length;
for (let i = 0; i < partyCount; i++) {
    // 从i的下一个政党开始组合，确保每个组合只生成一次
    for (let j = i + 1; j < partyCount; j++) {
        const total = testArr[i][1] + testArr[j][1];
        if (total > majorityThreshold) {
            validCombinations.push({
                parties: [testArr[i][0], testArr[j][0]],
                totalSeats: total
            });
        }
        // 处理3个政党的组合（示例数据共3个政党，按需扩展）
        for (let k = j + 1; k < partyCount; k++) {
            const total3 = testArr[i][1] + testArr[j][1] + testArr[k][1];
            if (total3 > majorityThreshold) {
                validCombinations.push({
                    parties: [testArr[i][0], testArr[j][0], testArr[k][0]],
                    totalSeats: total3
                });
            }
        }
    }
}

// 输出结果
console.log("符合条件的多数组合：");
validCombinations.forEach(comb => {
    console.log(`政党组合：${comb.parties.join("+")}，总席位：${comb.totalSeats}`);
});

代码说明 #

• 单个政党判断：直接遍历每个政党，若席位超过阈值则加入结果。
• 多政党组合去重：通过多层循环控制起始索引（如j从i+1开始，k从j+1开始），确保每个组合仅被生成一次，彻底避免顺序颠倒的重复项。

扩展递归版（适配任意数量政党） #

如果政党数量较多，循环嵌套会变得繁琐，用递归生成所有子集更灵活：

let testData = {
    "party1":19,
    "party2":29,
    "party3":10,
};
let testArr = Object.entries(testData);
const majorityThreshold = 30;

// 递归生成所有非空无序子集并筛选
function findValidCombinations(arr, threshold) {
    const result = [];
    // current：当前已选的政党组合；start：下一个政党的起始索引
    function backtrack(current, start) {
        if (current.length > 0) {
            const total = current.reduce((sum, [_, seats]) => sum + seats, 0);
            if (total > threshold) {
                result.push({
                    parties: current.map(([name]) => name),
                    totalSeats: total
                });
            }
        }
        for (let i = start; i < arr.length; i++) {
            backtrack([...current, arr[i]], i + 1);
        }
    }
    backtrack([], 0);
    return result;
}

// 调用递归函数并输出
const validCombinations = findValidCombinations(testArr, majorityThreshold);
console.log("递归版结果：");
validCombinations.forEach(comb => {
    console.log(`政党组合：${comb.parties.join("+")}，总席位：${comb.totalSeats}`);
});

示例输出 #

针对你的测试数据，运行代码后会输出：

符合条件的多数组合：
政党组合：party1+party2，总席位：48
政党组合：party2+party3，总席位：39
政党组合：party1+party2+party3，总席位：58

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