Итак, у меня есть этот код, который работает и возвращает True, если есть 2 подсписка с одинаковой суммой (1/2 от общей суммы), подробнее о Разделить сумму равных подмножеств
Пример:
s = Solution()
print(s.canPartition([3,10,9,2]))
# output [3, 9] , [10, 2]
В моем коде выполняются итерации индексов, и каждая итерация разделяется на 2 способа - первый способ - это прибавление значения к сумме .. второй способ - двигаться дальше без добавления значения. если один из способов возвращает True, это говорит о том, что решение найдено.
Сложность времени должна быть 2 ^ n, но из-за динамического программирования она была уменьшена до O (n)
Теперь моя проблема, которую я пытался выяснить, заключается в том, как вернуться к «Истинному корню» и распечатать все элементы, принадлежащие корню (надеюсь, половина от общей суммы)
Что я имею в виду под «истинным корнем» - это как-то, когда я возвращаю First True (это означает, что я нашел сумму), и для этого у меня уже есть элементы. Пример :
[3,10,9,2]
# output [3, 9] , [10, 2]
Tree of recursive:
[]
/ \
[3] []
/ \ \
[3,10] [3] []
/ / \
[3,9] # THE Root returing firt true
Код:
class Solution:
def canPartition(self, nums: List[int]) -> bool:
def helper(s1, s2, i, memo):
# recursion
hashed = (s1 + s2)
if hashed in memo.keys():
return memo[hashed]
if s1 == s2: # we have 2 groups of sums that sums total
return True
if s1 > s2: # we have too big group
return False
if i == len(nums): # the end
return s1 == s2
# 2 options : move to next index with/witohut counting index
memo[hashed] = helper(s1 + nums[i], s2, i + 1, memo) or helper(s1, s2, i + 1, memo)
return memo[hashed]
# begin
s = sum(nums) # sum
memo = {} # dynamic programing
if s % 2 == 0: # odd sum can't be divided equally
return helper(0, s // 2, 0, memo)
return False
Пример для лучшего понимания моего желаемого результата:
s = Solution()
print(s.canPartition([3,10,9,2]))
# output [3, 9] , [10, 2]
