Собеседование / 3 задание

Задание

Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых будет равняться 10.

Уточнения

Некоторые моменты в задании не оговорены, поэтому будем считать что:

  1. порядок комбинаций и чисел в комбинации не важен.
  2. если во входящем массиве есть повторения — примем их за разные элементы.

Сразу сделаем функцию для поиска произвольной суммы — это несложно, но потом может пригодиться.

Тестовые значения

Формат: входящий массив / требуемая сумма => массив всех комбинаций.

[ 7, 10, 2, 5, 3 ] / 10 => [ [ 10 ], [ 3, 7 ], [ 2, 3, 5 ] ]
[ 7, 10, 2, 5, 3, 1 ] / 10 => [ [ 10 ], [ 3, 7 ], [ 2, 3, 5 ], [ 1, 2, 7 ] ]
[ 7, 10, 2, 5, 3, 3 ] / 10 => [ [ 10 ], [ 3, 7 ], [ 3, 7 ], [ 2, 3, 5 ], [ 2, 3, 5 ] ] //повторения
[ 6 ] / 10 => [ ]
[ 28 ] / 10 => [ ]

Алгоритм работы

Задача сводится к рекурсии, ведь если мы используем в комбинации какой-то элемент E — то требуемая сумма уменьшается на значение E, и нужно провести поиск таких же комбинаций уже для массива без этого элемента.

Идём в цикле по всем элементам массива. Используя какой-то элемент E входящего массива, мы убираем его из рассмотрения, и уменьшаем требуемую сумму на его значение. Получив новый массив (с выколотым элементом E) и новую требуемую сумму, мы:

  1. если сумма равна 0 — нашли конечный элемент цепочки комбинации
  2. если сумма не равна 0 или новый массив равен [] — отбрасываем всю цепочку
  3. иначе — повторяем тот же процесс для новых массива и суммы.

В конце функции нужно также передать обратно сам этот элемент E.

Поскольку у меня нет строгого доказательства этого алгоритма, проверим его результат работы автоматизированными тестами — для большого количества случайных входных данных сравним результаты этого алгоритма и «глупого» алгоритма (простое перечисление всевозможных комбинаций значений, и проверка их сумм), и будем считать это достаточным доказательством.

Вообще говоря, задача является модификацией известной задачи о ранце, и мой вариант решения похож на метод ветвей и границ.

Листинг программы

/*
Быстрый алгоритм
*/
function find_optimized (task) {
var results=[], new_tasks=[];
for(i in task.ar)
// Нашли элемент = требуемой сумме? Это будет концом цепочки.
if(task.sum==task.ar[i]) results.push([task.ar[i]]); else
// Если поиск небесполезен - попробуем поискать, начиная с текущего элемента
if((task.ar.length-1>i)&&(task.sum>task.ar[i])) {
// Рекурсия с новой (меньшей) суммой и входным массивом с выколотым текущим элементом.
sub_array=find_optimized( {prev: task.ar[i], sum: task.sum-task.ar[i], ar: task.ar.slice(i*1+1)});
// Складываем в тот же плоский массив результаты поиска
for(i in sub_array[1]) results.push([sub_array[0]].concat(sub_array[1][i]));
}
// Если не на вершине стека - вернём предыдущий элемент цепочки. Если что-то нашли - вернём ещё и массив результатов.
return ((results.length==0) ? task.prev:(task.prev==undefined ? results:[task.prev, results]));
}

/*
Медленный, но гораздо более простой алгоритм для сравнения результатов
*/
function find_silly (task) {
var sub_arrays=[{ar: task.ar, processed: false}], i=0, full_processed=false;
// Просто перечисляем всевозможные комбинации. Нашли в sub_arrays какой-нибудь массив A - разбиваем
// его на все подмассивы без одного элемента, и вставляем результат обратно в sub_arrays. Сам массив A
// помечаем "обработанным".
while(!full_processed) {
if(!sub_arrays[i].processed) {
for (j in sub_arrays[i].ar)
sub_arrays.push({ar: sub_arrays[i].ar.slice(0, j).concat(sub_arrays[i].ar.slice(j*1+1)),
processed: (sub_arrays[i].ar.length>2?false:true)});
sub_arrays[i].processed=true;
}
full_processed=true;
for(j in sub_arrays)
full_processed=full_processed&sub_arrays[j].processed;
i++;
}
// Чистим массив от повторений с помощью вспомогательного объекта
var hash={};
for(i in sub_arrays) hash[sub_arrays[i].ar]=null;
sub_arrays=[];
for(i in hash) {
ar=i.split(',').map(function(value) { return value*1; });
if(ar.reduce(function(previousValue, currentValue){
return previousValue+currentValue;
})==task.sum) sub_arrays.push(ar);
}
return sub_arrays;
}

task = {sum: 10, ar: [7, 10, 2, 5, 3, 1]};

array_optimized=find_optimized(task);
array_silly=find_silly(task);

console.log(array_optimized);
console.log(array_silly);

Юнит-тест

var test = function () {
total_test=true;
for(test_i=0; test_i<10; test_i++)
{
task={sum: Math.round(Math.random()*20), ar: []}
len=2+Math.round(Math.random()*4);
for(j=0;j<1*len;j++) task.ar.push(1+Math.round(Math.random()*10));

array_optimized=find_optimized(task);
array_silly=find_silly(task);
for(i in array_optimized) {
found=false;
for(j in array_silly)
for(k in array_silly[j]) found&=(array_silly[j][k]==array_optimized[i][k]);
total_test&=found;
}
}
return (total_test==0);
}

Сравниваем результаты работы быстрого метода и точного метода. Код проходит тесты на наборе из 100 случайных заданий — с большой вероятностью можно утверждать, что алгоритм и код правилен.

Скорость работы

Проверим скорость алгоритмов с помощью jsperf.com — умный алгоритм в сто раз быстрее на массиве из 5 чисел.

Сложность алгоритма — не более O(2n).

Нажмите кнопку «тест»
Ссылка на основную публикацию