рекурсивный возврат для перечисления всех подмножеств с заданной суммой?

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

# arr -- the array
# n -- length of the array
# target_sum -- sum we want
# target_arr -- subarray we test for having the right sum
# ite -- iterator

def subset_sum(arr,n,target_sum,target_arr=[],ite=0):
    for i in range(ite,n):
        target_arr.append(arr[i])
        if sum(target_arr)==target_sum:
            print (target_arr, len(target_arr))
            target_arr.pop()
            subset_sum(arr,n,target_sum,target_arr,ite+1)
            return
        subset_sum(arr,n,target_sum,target_arr,i+1)
        target_arr.pop()

subset_sum([1,2,3,4],4,4)
[1, 3] 2
[1, 3] 2
[4] 1
[4] 1
[4] 1
[4] 1.

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

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


python recursion recursive-backtracking
person Glassjawed    schedule 07.06.2019    source источник
comment
Что это за язык?   -  person Enigmativity    schedule 07.06.2019
comment
Это в Питоне.   -  person Glassjawed    schedule 07.06.2019

Ответы (1)


arrow_upward
1
arrow_downward

Где в моем коде возникают повторы?

Я собираюсь немного изменить ваш код: он будет возвращать результаты, а не печатать их; он переставит свои аргументы так, что target_array не нужно будет передавать; он будет использовать еще более простой пример ввода с дубликатами:

def subset_sum(array, target_sum, start=0, target_array=[]):  # dangerous default value
    solutions = []

    for idx in range(start, len(array)):
        target_array.append(array[idx])

        if sum(target_array) == target_sum:
            solutions.append(list(target_array))
            target_array.pop()
            solutions.extend(subset_sum(array, target_sum, start + 1))
            break

        solutions.extend(subset_sum(array, target_sum, idx + 1))

        target_array.pop()

    return solutions

print(*subset_sum([1, 2, 3], 4))

Но у него все та же проблема с дублированием:

> python3 test.py
[1, 3] [1, 3]
>

Теперь я добавлю оператор отладочной печати:

        target_array.pop()
        print(f"print(*subset_sum({array}, {target_sum}, {start}, {target_array}))")
        solutions.extend(subset_sum(array, target_sum, start + 1))

Теперь, когда мы запустим его, мы получим:

> python3 test.py
print(*subset_sum([1, 2, 3], 4, 1, [1]))
print(*subset_sum([1, 2, 3], 4, 2, [1]))
[1, 3] [1, 3]
>

Мы можем подтвердить, заменив наш первоначальный вызов двумя вышеприведенными, что оба они производят одинаковый результат. Проведя небольшое исследование на основе print, мы можем определить, что первое является результатом рекурсивного вызова внутреннего цикла, а второе — результатом рекурсивного вызова внешнего цикла. В вызове нет дублирования (аргументы), но два разных вызова дают одинаковый результат.

Вы можете рвать на себе волосы, пытаясь это исправить, или просто заменить solutions на set вместо list и позволить Python отфильтровать дубликаты в исходном примере вызова:

def subset_sum(array, target_sum, start=0, target_array=[]):  # dangerous default value
    solutions = set()

    for idx in range(start, len(array)):
        target_array.append(array[idx])

        if sum(target_array) == target_sum:
            solutions.add(tuple(target_array))
            target_array.pop()
            solutions |= subset_sum(array, target_sum, start + 1)
            break

        solutions |= subset_sum(array, target_sum, idx + 1)

        target_array.pop()

    return solutions

print(*subset_sum([1, 2, 3, 4], 4))

С выходом:

> python3 test.py
(1, 3) (4,)
>
person cdlane    schedule 13.06.2019