Все перестановки целых чисел соответствуют определенной сумме

Question

Я хотел сгенерировать все перестановки из списка целых чисел [3,5,7,9], в результате чего было задано определенное значение 15. Я реализовал это, все в порядке.

def add_next(seq, count, m): 
    s = sum(seq) 
    if s == m: 
     count += 1 
     print(seq) 
    elif s < m: 
     for i in [3,5,7,9]: 
      add_next(seq + [i], count, m) 
    else: 
     return count 

add_next([], 0, 15) 

Выход:

[3, 3, 3, 3, 3] 
[3, 3, 9] 
[3, 5, 7] 
[3, 7, 5] 
[3, 9, 3] 
[5, 3, 7] 
[5, 5, 5] 
[5, 7, 3] 
[7, 3, 5] 
[7, 5, 3] 
[9, 3, 3] 

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

Я пробовал:

def add_next2(seq, count, m): 
    s = sum(seq) 
    if s == m: 
     count += 1 
     print(seq) 
    elif s < m: 
     for i in [3,5,7,9]: 
      count = add_next2(seq + [i], count, m) 
    else: 
     return count 

add_next([], 0, 15) 

но Retuns ошибку TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'. Таким образом, count - None. Зачем?

Другой вариант заключается в том, как перезаписать эту функцию, чтобы преобразовать ее в генератор и получить выходные строки один за другим?

Answer 1

Если вы просто подсчет успешных рекурсивные результатов, вам не нужно «кол 'как параметр. Вы можете просто вернуть успешные результаты как 1 и безуспешно, как 0, позволяя им накапливаться.

EDIT 2 Немного более кратким, но остается читаемым

def add_next(seq, m): 
    s = sum(seq) 
    count = 1 if s == m else 0 
    if s < m: 
     for i in [f for f in [3,5,7,9] if s + f <= m]: 
      count += add_next(seq + [i], m) 
    return count 

print(add_next([], 15)) 

EDIT Вы также можете отфильтровать [3,5,7,9] список, так что ваш для я в цикле имеет дело только с элементы, которые имеют успех.

for i in [f for f in [3,5,7,9] if s + f <= m]: 

Answer 2

Ваша рекурсивная функция не возвращает значение для s <= m. Верните что-то из вашей функции для этих случаев, в противном случае вместо этого возвращается None.

Скорее всего, вы хотите вернуться count во всех случаях:

def add_next2(seq, count, m): 
    s = sum(seq) 
    if s == m: 
     count += 1 
    elif s < m: 
     for i in [3,5,7,9]: 
      count = add_next2(seq + [i], count, m) 
    return count 

Это то работает:

>>> def add_next2(seq, count, m): 
...  s = sum(seq) 
...  if s == m: 
...   count += 1 
...  elif s < m: 
...   for i in [3,5,7,9]: 
...    count = add_next2(seq + [i], count, m) 
...  return count 
... 
>>> add_next2([], 0, 15) 
11