Как я могу помнить этот алгоритм суммирования подмножества?

Question

Это не то же самое, что и этот вопрос: find all subsets that sum to a particular value Как я не просто должен count общее количество подмножеств, но сохранить все подмножества и вернуть его.

Я написал простой (экспоненциальный) алгоритм, который находит подмножества подведения к определенной цели:

Eg: 
arr = [1,2,3,4,5,6,7,8] 
Possible subsets: 
5 
4,1 
3,2 

Это мой алгоритм

п -> индекс списка (начинается с конца)

цель -> сумма подмножеств Я хочу, чтобы создать

arr = [1,2,3,4,5,6,7,8] 
def subset_sum(arr, n, target, result): 

    if target == 0: 
     print result 
     return 

    if target < 0 or n < 0: 
     return False 



    subset_sum(arr, n-1, target - arr[n], result + str(arr[n])) 
    subset_sum(arr, n - 1, target, result) 

print subset_sum(arr, len(arr) - 1, 5, '') 

Я хочу OPM сделайте это, возможно, путем memoization. Но я с трудом выяснить, что должно быть состояние этой функции (Должна ли она быть n и target? .. но я не вижу, что повторяется)

Answer 1

«Я не вижу его повторяться ".
Рассмотрим простой пример массива, имеющего повторяющиеся значения или нули.
, например. arr = [3,2,4,5,0,5], и вы ищете подмножества, сумма которых равна 7, см. здесь, что индекс 3 (если начальный индекс равен 1), попадает в результирующий 2 дважды, один раз, когда последние 5 включены в ответ и снова, когда это исключено из ответа
Для большей наглядности смотрите здесь другой пример
arr = [5,2,3,6,3,5,8], вы ищете сумма 12, вы выбираете последний индекс, т. е. 7, и оставляете 6,5, следовательно, достигая индекса 4 с суммой 4, или вы оставляете индекс 7, а также выбираете индекс 6,5 и снова достигаете индекса 4 с суммой 4.
Так вот необходимость запоминания.
Вы также можете решить проблему n снизу вверх, построив матрицу из n строк и столбцов суммы, или наоборот.