Как превратить это рекурсивное решение в решение DP?

Question

Привет, я разработал рекурсивное решение для проблемы равных подмножеств разделов (https://leetcode.com/problems/partition-equal-subset-sum/) на LeetCode, которое принимается:

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) < 2:
            return False
        if sum(nums) % 2 != 0:
            return False
        target = sum(nums) // 2
        # if the maximum number in nums goes larger than target, 
        # then this maximum number cannot be partitioned into any subarray
        # hence there's no solution in this case, return False early
        if max(nums) > target:   
            return False
        nums.sort(reverse = True)
        return self.helper(nums, 0, target, 0)

    def helper(self, nums, index, target, curr):
        # since "target" value is derived from dividing total sum, 
        # we only need to search for one sum that makes target value in the array
        # the rest is guaranteed to sum up to "target" 
        if curr == target:
            return True
        for i in range(index, len(nums)):
            if curr + nums[i] > target:
                continue
            if self.helper(nums, i + 1, target, curr + nums[i]):
                return True
        return False

Однако, как продолжение, что было бы лучшим способом на самом деле вернуть два подмножества вместо просто True / False. Как бы выглядел код с сохраненными подмножествами, если бы мне пришлось обновить вышеупомянутый существующий код? Я один из тех людей, которые начинают с DP. Заранее спасибо.

Answer 1

Разобрался с решением:

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) < 2:
            return []
        if sum(nums) % 2 != 0:
            return []
        target = sum(nums) // 2
        if max(nums) > target:   
            return []
        nums.sort(reverse = True)
        res = []
        self.helper(nums, 0, target, [], res)
        return res

    def helper(self, nums, index, target, curr, res):
        if sum(curr) == target:
            res.append(list(curr))
            return
        for i in range(index, len(nums)):
            if sum(curr) + nums[i] > target:
                continue
            self.helper(nums, i + 1, target, curr + [nums[i]], res)