Блог

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

 def count_sets(arr, total):
    return rec(arr, total, len(arr)-1)


def rec(arr, total, i):
    print(arr, total, i)
    if total == 0:
        return 1
    if i < 0:
        return 0

    if arr[i] > total:
        return rec(arr, total, i-1)

    else:
        return rec(arr, total-arr[i], i-1)   rec(arr, total, i-1)

arr = [2,10,6,4]
print(count_sets(arr, 16))
  

программа работает без каких-либо ошибок, однако я не могу найти, как она работает.

Это алгоритм обратного отслеживания. При рекурсии rec(arr, total, i) выбирается последний элемент arr[i] в массиве rest, и вот две основные ситуации:

1. использование arr[i] : rec(arr, total-arr[i], i-1)
2. не используйте arr[i] : rec(arr, total, i-1) , и когда arr[i] > total , конечно, вы можете только не использовать его.

и мы должны иметь условие завершения для recursion , то есть:

1. [успех] найти подмассив, равный total: if total == 0: return 1
2. [не удалось] добраться до главы: if i < 0: return 0

Надеюсь, я проясню и прокомментирую, если у вас возникнут дополнительные вопросы. 🙂