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)