Итак, у меня есть этот код, который работает и возвращает True, если есть 2 подсписка с одинаковой суммой (1/2 от общей суммы). Узнайте больше о Разделение Равное Подмножество Sum
Пример:
s = Solution()
print(s.canPartition([3,10,9,2]))
# output [3, 9] , [10, 2]
Мой код выполняет итерацию индексов, и каждая итерация разделяется на 2 пути - первый способ - добавление значения к сумме. Второй способ - переход без добавления значения. если один из способов возвращает True, это говорит о том, что решение найдено.
Сложность времени должна быть 2 ^ n, но из-за динамического c программирования она была уменьшена до O (n)
Теперь моя проблема, которую я попытался выяснить, заключается в том, как отследить «True root» и распечатать все элементы, которые принадлежат root (возможно, половине общей суммы)
Что Я имею в виду, что «истина root» - это как-то, когда я возвращаю Первое Истинное (это значит, что я нашел сумму), и для этого у меня уже есть предметы. Пример:
[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]