编辑代码



const dats = [2, 3, 1, 5,3, 4, 2,5];

function func(A) {
    let i;
    let j;

    let n2 = A.length;
    let n = n2 >> 1;
    let sum = A.reduce((s, n) => s + n);

    /** 
     * flag[i][j]:任意i个数组元素之和是j,则flag[i][j]为true 
     */
    let flag = []
    for (i = 0; i < A.length; i++) {
        flag[i] = [];
        for (j = 0; j < sum; j++) {
            flag[i][j] = false;
        }
    }
    flag[0][0] = true;
    for (let k = 0; k < n2; k++) {
        for (i = k > n ? n : k; i >= 0; i--) {
            // 两层外循环是遍历集合S(k,i)   
            for (j = 1; j <= sum; j++) {
                if (j >= A[k] && flag[i][j - A[k]]) {
                    flag[i + 1][j] = true;
                }
            }
        }
    }
    let res
    for (let j = (sum >> 1); j >= 0; j--) {
        // 这里可以通过二分法查找,数组个数平均值开始
        for (let i = 1; i < n2; i++) {
            if (flag[i][j] && flag[n2 -i][sum -j]) {
                console.log(`sum: ${sum}, i: ${i}, j: ${j}`);
                res = true
                break;
            }
        }
        if(res) break;
    }
}

func(dats)