function balance(arr1, arr2) {
let all = arr1.concat(arr2);
//all.sort((a, b) => a - b); //Для исключения одинаковых.
let all_sum = all.reduce((a,b)=>a+b,0);
let len = all.length;
let cnt = Math.floor(len * 0.5);
let arr_result = new Array(cnt); //Массив выбранных индексов
let idx_begin = 0; //Начальная глубина перебора (индекс в arr_result)
let sum_begin = 0; //Начальная сумма частично перебранных элементов
if (cnt === len * 0.5) { //Оптимизация
arr_result[0] = 0;
idx_begin = 1;
sum_begin = all[0];
}
let min_diff = all_sum; //Присваиваем какое-то заведомо большое число.
let arr_answer; //Итоговый ответ
//Проверяем следующий уровень глубины
//idx - глубина, sum - сумма всех элементов до этого
function check(idx, sum) {
if (idx === cnt) { //Конец перебора. Проверяем, подходит ли.
let diff = Math.abs((all_sum - sum) - sum);
if (diff < min_diff) { //Подходит
min_diff = diff; //Запоминаем новый лучший результат.
arr_answer = arr_result.slice(); //Копируем
}
return;
}
//Иначе идем дальше вглубь на следующий уровень.
let start = idx === 0 ? 0 : arr_result[idx-1] + 1;
let max = len - cnt + idx;
for(let i = start; i <= max; i++){ //Ключевой цикл алгоритма
//if (i > start && all[i] === all[i-1]) continue;
arr_result[idx] = i;
check(idx+1, sum+all[i]); //Рекурсия
}
}
check(idx_begin,sum_begin); //Начать перебор. Поехали!
arr1 = [];
arr2 = [];
//Фасуем полученный ответ по массивам уже в виде значений.
let j = 0;
all.forEach((e,i)=>{
if (i === arr_answer[j]) {
arr1.push(e);
j++;
} else arr2.push(e);
});
return {
arr1: arr1,
arr2: arr2,
sum1: arr1.reduce((a,b)=>a+b,0),
sum2: arr2.reduce((a,b)=>a+b,0),
}
}
var arr1 = [10, 300, 25, 75];
var arr2 = [50, 125, 500, 10];
balance(arr1, arr2);
