如何实现将整数数组拆分为两个等长等和子集的ArrayChallenge函数？

这是带长度限制的子集和问题，核心约束有三个：

• 选出的子集长度严格等于原数组长度的一半
• 选出的子集元素总和等于原数组总和的1/2
• 最终输出要排序后按首元素大小顺序拼接两个子集

• 首先计算原数组总和，如果总和为奇数，直接返回空（无合法解）
• 计算目标子集和target = 总和 / 2，目标子集长度k = arr.length / 2
• 回溯搜索符合长度和总和要求的子集，可加剪枝优化提升效率：
  • 当前已选元素个数超过k直接终止
  • 当前已选元素总和超过target直接终止
  • 剩余未选元素全部加进来也凑不够k个直接终止
• 找到合法子集后，将剩余元素归为另一个子集
• 两个子集分别做升序排序，比较首元素，首元素更小的子集放在前面
• 把两个子集的元素按顺序拼接成逗号分隔的字符串即可

function ArrayChallenge(arr) {
    const total = arr.reduce((a, b) => a + b, 0);
    // 总和为奇数直接无解
    if (total % 2 !== 0) return '';
    const target = total / 2;
    const k = arr.length / 2;
    let resSubset = null;

    // 回溯找符合条件的子集
    function backtrack(start, currentSum, currentList) {
        if (currentList.length === k) {
            if (currentSum === target) {
                resSubset = [...currentList];
                return true;
            }
            return false;
        }
        // 剪枝：剩余元素不够凑k个
        if (currentList.length + (arr.length - start) < k) return false;
        // 剪枝：当前和已经超过target
        if (currentSum > target) return false;

        for (let i = start; i < arr.length; i++) {
            currentList.push(arr[i]);
            if (backtrack(i + 1, currentSum + arr[i], currentList)) return true;
            currentList.pop();
            // 跳过重复元素避免重复搜索
            while (i < arr.length - 1 && arr[i] === arr[i + 1]) i++;
        }
        return false;
    }

    // 先排序原数组提升剪枝效率
    arr.sort((a, b) => a - b);
    backtrack(0, 0, []);
    if (!resSubset) return '';

    // 统计频率筛选另一个子集
    const freq = {};
    resSubset.forEach(num => freq[num] = (freq[num] || 0) + 1);
    const otherSubset = arr.filter(num => {
        if (freq[num]) {
            freq[num]--;
            return false;
        }
        return true;
    });

    // 两个子集排序后按首元素顺序拼接
    resSubset.sort((a, b) => a - b);
    otherSubset.sort((a, b) => a - b);
    const finalArr = resSubset[0] < otherSubset[0] ? [...resSubset, ...otherSubset] : [...otherSubset, ...resSubset];
    return finalArr.join(',');
}

// 测试示例
console.log(ArrayChallenge([16,22,35,8,20,1,21,11])); // 输出 1,11,20,35,8,16,21,22

• 提前对原数组排序，可以让剪枝更高效，提前排除超过target的分支
• 跳过重复元素的优化可以避免大量重复搜索，大幅提升存在重复元素时的运行效率
• 找到第一个合法子集就直接返回，不需要遍历所有可能，减少不必要的计算

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