Created
January 15, 2014 19:16
-
-
Save pshezgyr/8442472 to your computer and use it in GitHub Desktop.
Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых будет равняться 10
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых будет равняться 10 | |
* | |
* @see http://company.yandex.ru/job/vacancies/dev_int_yaservices.xml | |
* @param {Array} ITEMS | |
* @param {Integer} target | |
* @example findCombinations([ 7, 10, 2, 5, 3, 1 ], 10) => [[7, 2, 1], [7, 3], [10], [2, 5, 3]] | |
* @returns {Array} | |
*/ | |
function findCombinations (ITEMS, target) | |
{ | |
var results = [], | |
i = 0, | |
l = ITEMS.length, | |
item; | |
for( ; i<l; i++ ) | |
{ // Проходим массив значений | |
item = ITEMS[i]; // Текущее значение | |
if( item > target ) continue; // Выходит за цель, отбросили, выходим | |
if( item == target ) { results.push([item]); continue; } // Оно, цепляем, выходим | |
var subResults = findCombinations(ITEMS.slice(i+1), target - item); // Ищем возможные варианты, исключая текущее значение | |
if( ! subResults.length ) continue;// Возможностей нет, отбросили, выходим | |
// console.log("subResults for", item, "is", subResults); // Все возможные варианты для текущего значения | |
for( var j=0, k=subResults.length; j<k; j++ ) | |
results.push([item].concat(subResults[j])); // Склеиваем результат | |
}; | |
return results; | |
}; | |
console.log( findCombinations([ 7, 10, 2, 5, 3, 1 ], 10) ); |
Сокращаем массив до [10, 2, 5, 3, 1 ] и в нем ищем массив, сумма цифр которого уже равно 3.
Это вроде как ясно, а когда функция доходит до единицы (наверное уже в 3 рекурсионной функции, запутался), единица добавляется в results, так ? И вот на дальнейшем этапе куда мы вылетаем и что ищем, не ясно? И мне как казалось далее в results должна была попасть тройка, но попала 2. )))))
2 + 7 < 10
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
На первом шаге первая 7.
Она меньше 10
Сокращаем массив до [10, 2, 5, 3, 1 ] и в нем ищем массив, сумма цифр которого уже равно 3.