Использования рекурсии для поиска всех комбинаций элементов массива целых чисел

Question

я работаю над этой проблемой с Coderbyte помощью JS:

имеет функцию ArrayAdditionI (обры) принимает массив чисел, хранящийся в обрах и вернуть string true, если любая комбинация чисел в массиве может быть добавлена ​​до максимального количества в массиве, иначе верните строку false. Например: если arr содержит [4, 6, 23, 10, 1, 3], вывод должен возвращать true, потому что 4 + 6 + 10 + 3 = 23. Массив не будет пустым, не будет содержать все те же элементы, и могут содержать отрицательные числа.

Проблема кажется спелой для рекурсивного решения, учитывая характер ветвления необходимости изучения различных комбинаций элементов массива. Я также хотел бы использовать рекурсию, чтобы получить дополнительную практику. Я все еще очень новичок в кодировании.

Вот решение, которое я придумал, и я был очень рад об этом, пока я не начал тестирование и обнаружил, что это вовсе не решение:

function ArrayAdditionI(arr) { 
    // sorting the array to easily remove the biggest value 
    var sArr = arr.sort(function (a, b) { 
    return a-b;}); 
    // removing the biggest value 
    var biggest = sArr.pop(); 
    // count will be iterated to stop the recursion after the final element of the array has been processed 
    var count = 0; 
    function recursion (start, i) { 
    if (sArr[i] + start === biggest) { 
     return true; 
    } 
    else if (start + sArr[i] < biggest) { 
     return recursion(start + sArr[i], i+1); 
    } 
    else if (start + sArr[i] > biggest && count < sArr.length) { 
     count++; 
     return recursion(0, count); 
    } 
    else { 
     return false; 
    } 
    } 
    return recursion(0,0); 
} 

Этот код работает только тогда, когда элементы массива которые могут быть суммированы для выполнения базового случая, смежны друг с другом; вызов ArrayAdditionI ([1,2,3,4]), например, не будет работать, потому что два элемента, которые должны быть суммированы для достижения целевого значения («1» в позиции 0 и «3» в позиции 2), являются не смежные.

Мой поток будет возвращать 1, затем 1 + 2, затем 1 + 2 + 3, затем 2, затем 2 + 3, затем 3 и, наконец, вернуть false, так как цель (4) не была достигнута.

Я могу представить, как правильное решение должно проходить через данный массив, но я не знаю, как это сделать через рекурсию. Для данного массива [1,2,3,4] поток должен проверять результаты в этом шаблоне: (position0, pos0 + pos1, pos0 + pos2, pos0 + pos1 + pos2, pos2, pos2 + pos3, pos3). Может ли кто-нибудь подтолкнуть меня? Я собираюсь подумать об этом больше, прежде чем я сплю через час и даю ему свежий выход утром. Может быть, моему мозгу просто нужна пополнение.

Опять же, я на самом деле новичок в этом, если бы я сделал некоторые глупые ошибки, пожалуйста, дайте мне знать, я узнаю от них. Благодаря!

Answer 1

function ArrayAdditionI (arr) { 
    var sArr = arr.sort(function (a,b) { 
     return a-b; 
    }); 
    var biggest = sArr.pop(); 
    function recursion (start, indx) { 
     if (start + sArr[indx] === biggest) { 
      return true; 
     } 
     else if (sArr.length < indx) { 
      return false; 
     } 
     else if (start + sArr[indx] < biggest) { 
      return recursion(start + sArr[indx], indx + 1) || recursion(start, indx+1) 
     } 
     else { 
      return false; 
     } 
    } 
    return recursion(0,0); 
} 

Answer 2

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

function ArrayAdditionI(arr) { 
    // sorting the array to easily remove the biggest value 
    // slice added to prevent original array modification 
    var sArr = arr.slice().sort(function (a, b) { 
     return a - b; 
    }); 
    // removing the biggest value 
    var biggest = sArr.pop(); 
    function recursion(start, i) { 
     var result = false; 
     // looking over all rest values of array 
     for (var j = i; j < sArr.length && !result; j++) { 
      if (sArr[j] + start === biggest) { 
       result = true; 
      } 
      else if (start + sArr[j] < biggest) { 
       result = recursion(start + sArr[j], j + 1); 
      } 
     } 
     return result; 
    } 
    return recursion(0, 0); 
}