377. Combination Sum IV

LeetCode задача 377

Задача

Дан массив различных целых чисел nums и целевое целое число target от 1 до 1000. Нужно вернуть количество возможных комбинаций, которые в сумме дают target.

Подсказки

1. Построить дерево решений
2. Задачу можно решить путем разложения ее на меньшие подзадачи с помощью динамического программирования.

Нахождение целевого значения в дереве решений

Подход

Если целевое значение - target=7 и nums=[2, 3, 4], то в дереве решений может быть несколько путей до этого числа. Например: 2-2-3, 2-3-2, 3-2-2, 3-4, 4-3, 5-2.

Во время подсчета различных путей мы получаем различные суммы, например: 2-2-3, сначала сумма 2, потом 4, потом 7. Следующи возможный путь начинается с 3. Чтобы проверить, подходит данный путь или нет, мы можем рассчитать недостающее число до target: 7-3=4. Мы получили 4, но ранее мы уже получали такую сумму и знаем, что если на данном этапе мы хотим знать будет ли какое количество вариантов для суммы 4, то в итоге мы найдем решение.

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

Мы будем использовать массив sums, где sums[s] будет хранить количество комбинаций, которые дают сумму s.

Для каждого числа s от 1 до target, мы будем итерировать по каждому числу в nums и прибавлять sums[s-num] к sums[s].

Пример:

sums[4] = sums[4-2] + sums[4-4] + sums[4-4]

Почему мы рассматриваем числа от 1 до target?

Целью является поиск всех возможных комбинаций чисел из nums, которые в сумме дают target. Начиная с 1 и заканчивая target, мы стремимся найти все возможные комбинации для каждого промежуточного значения. Таким образом, когда мы достигаем target, у нас уже будут вычислены комбинации для всех предыдущих значений, что позволит быстро найти ответ для target.

Зачем нам нужен индекс с нулевым значением в массиве?

Значение sums[0] = 1 может показаться не совсем интуитивным, но оно имеет особый смысл. Это значение говорит нам о том, что есть один способ получить сумму 0 — не использовать ни одного числа из nums. Это начальное условие необходимо для корректной работы алгоритма, так как при добавлении каждого нового числа из nums к уже найденным комбинациям мы будем обращаться к этому значению.

Рассмотрим пример. Пусть nums = [1,2,3] и target = 4. Когда мы рассматриваем число 1 (первый шаг итерации), наш алгоритм будет искать число комбинаций, которые дают сумму 1 - 1 = 0. И здесь значение sums[0] приходит на помощь: благодаря ему алгоритм “понимает”, что существует одна такая комбинация.

Алгоритм

1. Создаем список sums с длиной target + 1 и заполняем его нулями. Этот список будет представлять количество комбинаций, которые приводят к определенной (промежуточной) сумме.
2. Устанавливаем sums[0] в 1, так как есть только один способ получить сумму 0: при пустом nums.
3. Основной цикл (построение таблицы):
   1. Перебираем все возможные суммы от 1 до target (включительно). Допустим, текущее число обозначено как s
      1. Теперь перебираем каждое число n из nums.
         1. Находим остаточную сумму s - n
         2. Прибавляем к sums[s] значение sums[s-n], так как любая комбинация, ведущая к s-n, может быть дополнена числом n, чтобы достичь s.

Решение

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        sums = [0] * (target + 1)
        sums[0] = 1  # entrypoint of dynamic p: sum 0 can be only in case if nums is empty

        for s in range(1, target + 1):
            for n in nums:                      # check all paths
                remainder = s - n              
                if remainder >= 0:              # use only positive indexes (sums)
                    sums[s] += sums[remainder]  # count to previous results

        return sums[target]

Данное решение можно отобразить с использованием словаря для всех сумм:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        sums = {0:1}

        for s in range(1, target + 1):
            sums[s] = 0
            for n in nums:                      
                remainder = s - n              
                sums[s] += sums.get(remainder, 0)

        return sums[target]