Python: рекурсивная функция. Как вернуть все подмножества targetsum

Я не уверен в этом, но при определении функции в python и предоставлении 2 наборов кодов фактически не выполняется второй набор кода при вызове функции. У меня такая же проблема с другим проектом. И я не получил ответов, кроме как сказать, что я сделал что-то не так в коде!!!

Я проверил ваш код. Чего мне не хватало, так это

• Неправильное размещение return и сохранение значений внутри комбо (set вместо списка).

   def howsum(targetsum,numbers,combo=None):
       if combo == None:
           combo = set()
       if targetsum == 0: 
           return [ ]
       if targetsum < 0: 
           return None
  
       for idx,number in enumerate(numbers):
           remainder = targetsum - number
           if howsum(remainder,numbers[idx:],combo) != None:
               combo.add(number)
       else:
           return combo
       return None
  

print(howsum(7,[7,3,4,2,5]))

Надеюсь это поможет. Хотя это дает вам решение, я бы рекомендовал использовать другой способ решения таких проблем (решения twoSum) или подход с двумя указателями с O (n).

Добавлено запоминание, однако с 1 внутри наборов num. результаты пошли наперекосяк.

def best_sum(target_sum, numbers,memo=None):
    if memo == None:
      memo = dict()
    
    if target_sum in memo:
      return memo[target_sum]
  
    if target_sum == 0: return []
    if target_sum < 0: return None
    
    shortest_combination = None

    for num in numbers:
        remainder = target_sum - num
        remainder_combination = best_sum(remainder, numbers,memo)
        if remainder_combination != None:
            remainder_combination.append(num)
            combination = remainder_combination
            if shortest_combination == None or len(combination) < len(shortest_combination):
                shortest_combination = combination
    memo[target_sum] = shortest_combination
    return shortest_combination

print(best_sum(100,[5,1,25]))

Этот код по ответу, опубликованному DarylG, работает. Изменив .append на [*list,var] Однако я не понимаю, почему результат отличается между функцией append и *

def best_sum(target_sum, numbers,memo=None):
    if memo == None:
      memo = dict()
    
    if target_sum in memo:
      return memo[target_sum]
  
    if target_sum == 0: return []
    if target_sum < 0: return None
    
    shortest_combination = None

    for num in numbers:
        remainder = target_sum - num
        remainder_combination = best_sum(remainder, numbers,memo)
        if remainder_combination != None:
            combination = [*remainder_combination,num] #this line from append to *
            if shortest_combination == None or len(combination) < len(shortest_combination):
                shortest_combination = combination
    memo[target_sum] = shortest_combination
    return shortest_combination

print(best_sum(100,[5,1,25]))

Написал код, полностью соответствующий исходному JavaScript.

Хотя имена JavaScript будут работать, я провел рефакторинг имен функций и переменных, чтобы они соответствовали стилю Python, а именно:

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

Код

def best_sum(target_sum, numbers):
    if target_sum == 0: return []
    if target_sum < 0: return None
    
    shortest_combination = None

    for num in numbers:
        remainder = target_sum - num
        remainder_combination = best_sum(remainder, numbers)
        if remainder_combination != None:
            combination = [*remainder_combination, num] # Python * equivalent to JavaSscript ...
            if shortest_combination == None or len(combination) < len(shortest_combination):
                shortest_combination = combination
    
    return shortest_combination

Тест

print(bestSum(7, [3, 4, 7])) # Output: [7]

Использование мемоизации (т. е. кэширования)

def best_sum(target_sum, numbers, memo = None):
    if memo is None:
        memo = {0:[]}
    if target_sum < 0:
        return None
    if target_sum in memo:
        return memo[target_sum]

    shortest_combination = None

    for num in numbers:
        remainder = target_sum - num

        remainder_combination = best_sum(remainder, numbers, memo)
        if remainder_combination != None:
            combination = [*remainder_combination, num] # Python * equivalent to JavaSscript ...
            if shortest_combination == None or len(combination) < len(shortest_combination):
                shortest_combination = combination

    memo[target_sum] = shortest_combination

    return memo[target_sum]

print(best_sum(7, [3, 4, 7]))  # Output: 7
# Following very slow on non-memoized version
print(best_sum(100,[10,1,25])) # Output: [25, 25, 25, 25]

Помимо использования memo/любой переменной для запоминания, вы можете использовать метод functools.lru_cache. Просто не забудьте ввести тип ввода во время тестирования.

import functools

@functools.lru_cache(maxsize=4)
def howsum(targetnum, num_list):
    if targetnum == 0:
        return []
    if targetnum < 0:
        return None
    for num in num_list:
        rem = targetnum - num
        rem_val = howsum(rem, num_list)
        if rem_val is not None:
            rem_val.append(num)
            return rem_val
    return None

print(howsum(7, tuple([5, 3, 4, 7])))
print(howsum(8, tuple([3, 4, 2])))
print(howsum(300, tuple([7, 14])))