У меня возникли проблемы с визуализацией рекурсивных вызовов проблемы Combination Sum?

Question

Вопрос в том, чтобы найти все уникальные комбинации в отсортированном массиве, которые суммируются с заданным целевым значением.Для этого примера, скажем, кандидатов = [2,3,6,7] и целевой = 7.Я посмотрел несколько видео, и теперь я понимаю общий алгоритм решения этой проблемы.Я также посмотрел на решение, но у меня возникли некоторые проблемы с визуализацией рекурсивного дерева / каждого рекурсивного вызова в функции.

var combinationSum = function(candidates, target) {
    candidates.sort((a,b) => a-b)
    let result = []
    combSum(candidates, target, [], result, 0)
    return result 
};

function combSum(candidates, target, current, result, idx) {
    let n
    for (let i = idx; i < candidates.length; i++) {
        n = candidates[i]
        current.push(n)
        if (n === target) {
            result.push([...current])
        } else if (target > n) {
             combSum(candidates, target-n, [...current], result, i)
        }
        current.pop()
    }
 }

Я знаю, что первый шаг состоит в том, чтобы попробовать комбинации, начинающиеся с первого значения в массиве, равного 2. Таким образом, функция попытается [2], затем [2,2], затем [2,2,2], и на данный момент целью является 1, который меньше n, поэтому он пропускает оба оператора if и вытаскивает последние 2.Возвращает ли метод pop () неявный возврат к предыдущему вызову функции в стеке вызовов?Он вернул бы значение 2, которое никогда не использовалось, верно?Там нет базового случая, который сбивает меня с толку.

Кроме того, я знаю, что поскольку массив отсортирован, мы должны знать, что если что-то вроде [2,2,3,3] не работает, то любая другая комбинация, начинающаяся с префикса [2,2,3] тоже не сработает.Хотя я не понимаю, как код решает эту проблему - как он может пропустить эти комбинации?Как [2,2,3,6] и т. Д.

РЕДАКТИРОВАТЬ: Уже очень поздно, я понял в своем первоначальном посте, что я смотрел на другое целевое значение, которое добавляло мне путаницуисправил мой пост, чтобы отразить это.К сожалению !!

Answer 1

Этот ответ не затрагивает аспект визуализации, но ограничивается вашими вопросами по конкретным деталям.

Отборочные

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

Параметры combSum имеют следующее значение:

• candidates: пул номеров для выбора (упорядоченный массив)
• target: число для составления (целое число)
• current: частичная комбинация, которая в данный момент завершается (упорядоченный массив)
• result: найденные комбинации
  (псевдолексикографически упорядоченный массив - префиксы идут после их продолжений)
• idx: минимальный индекс элемента candidates для использования в вызове.

Концептуально candidates и idx объединяются в единый фактический параметр candidates.slice(i).

В рекурсии есть 2 инварианта:

• Элементы в массиве current, представляющие частично построенную комбинацию, которая в настоящее время завершается, не убывают.
• Последовательность строится слева направо.
  В частности, ни один рекурсивный вызов не изменяет элементы current, которые присутствовали при вызове.

Упорядочение кандидатов помогает избежать повторяющихся конструкций одной и той же последовательности. Помните, что в каждом рекурсивном вызове эффективный набор элементов-кандидатов равен candidates.slice(i) с i неубывающим, и в цикле каждого уровня рекурсии начальное значение i этого уровня начинается с текущего значения i от родительского уровня .

Обратите внимание, что это работает только в том случае, если в candidates нет дубликатов чисел, которые отображаются в комбинации результатов, в противном случае подпоследовательности, начинающиеся с этого числа, будут вычисляться несколько раз, давая несколько идентичных результатов (Попробуйте combinationSum([1,4], 4) и combinationSum([1,1,4], 4); если быть точным, этого не произойдет, если кратность в candidates будет равна кратности в каждом результате ... попробуйте combinationSum([2,2,5], 9) и combinationSum([2,5], 9))

1. База рекурсий
База рекурсии - это случай n >= target ...

2. Пропуск «невозможных» префиксов ... Если n === target, текущая частичная комбинация завершается и добавляется к результатам. Если n > target, текущая частичная комбинация не может быть успешно завершена (номера кандидатов будут только увеличиваться, а текущая слишком большая). Тем не менее, код не обслуживает это условие (это может быть с оператором if (n > target) break; в конце цикла).

3. Неявный возврат current.pop() восстанавливает частичную комбинацию, с которой начался текущий вызов combSum. Это его цель. Хотя технически pop возвращает некоторое значение, но это значение уже используется - это верхний элемент current на месте рекурсивного вызова!