有没有办法打印一个列表的 2 个相等和子列表？

Question

所以我这里有这段代码可以工作并且 returns 正确，如果有 2 个子列表具有相同的总和（总和的 1/2）阅读更多关于 Partition Equal Subset Sum

示例：

s = Solution()
print(s.canPartition([3,10,9,2]))
# output [3, 9] , [10, 2]

我的代码迭代索引，每次迭代分为两种方式 - 第一种方式是将值添加到 sum..第二种方式是在不添加值的情况下继续。如果其中一种方法 return 为真，则表示已找到解决方案。

时间复杂度应该是 2^n 但由于动态规划它已经减少到 O(n)

现在我试图弄清楚的问题是如何回溯 "True root" 并打印属于根的所有项目（希望是总和的一半）

我所说的 "true root" 的意思是，当我 return 第一个为真时（这意味着我已经找到了总和）并且这样我就已经有了这些项目。示例：

[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]

Answer 1

有用的提示

您的 helper 函数 returns True 或 False。在它 returns True 之前，尝试打印您在该递归中考虑的最后一个元素 nums[i]。

另一个提示

在 helper 中，您正在进行两次递归调用。

helper(s1 + nums[i], s2, i + 1, memo)
helper(s1, s2, i + 1, memo)

如果第 1 步的结果是 True，这意味着您的总和中保留了 nums[i]。您需要拆分 OR 语句，以便找出这一点。拆分时，如果第1步True，则不需要运行第2步

有没有办法打印一个列表的 2 个相等和子列表？

Is there a way to print 2 equally sum sub list, of a list?

python

algorithm

recursion

dynamic-programming

subset-sum