Рекурсивно пересекающаяся дилемма суммы подмножеств

Question

Я изучаю рекурсивную логику, что одной из проблем является сумма подмножеств. AFAI читай, есть совпадения, когда он запускается рекурсией. Но я не могу понять, как они есть. Кроме того, я прочитал, что для преодоления проблемы можно использовать DP, но я хочу понять , как рекурсия преодолевает проблему. Не могли бы вы представить пример с перекрытием?

Псевдо-код

def hasSum( array, start, sum):
   if sum == 0:
       return true

   if start > array.length - 1:
       return false;

   return hasSum(array, start + 1, sum - array[start])
           or hasSum(array, start + 1, sum)

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

Answer 1

Здесь наложение вызвано этой строкой:

return hasSum(array, start + 1, sum - array[start])
           or hasSum(array, start + 1, sum)

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