如何将分割等和子集递归解法转为DP并返回两个子集？

Hey there! Nice work getting the recursive solution accepted—let's tackle your two questions one by one, starting with converting that recursive approach to dynamic programming, then adjusting the code to return the actual subsets instead of just a boolean.

1. Converting the Recursive Solution to Dynamic Programming #

Your recursive approach is a classic backtracking solution, which works but has exponential time complexity (O(2ⁿ)) because it explores every possible combination of elements. Dynamic Programming (DP) will optimize this to O(n*target) time by eliminating redundant calculations using a memoization array.

This problem is a perfect fit for the 0-1 Knapsack model: we want to select a subset of elements whose sum equals target (half the total sum of nums).

Approach Explanation #

• DP State Definition: We'll use a 1D array dp where dp[j] represents whether we can form the sum j using any subset of the elements we've processed so far.
• Base Case: dp[0] = True (we can always form sum 0 by choosing no elements).
• Transition: For each element, we update the DP array from right to left (to avoid reusing the same element multiple times). For each sum j from target down to the element's value, dp[j] becomes True if either we could already form j without the element, or we can form j - num (so adding the current element gets us to j).

DP Code (1D Space Optimized) #

class Solution(object):
    def canPartition(self, nums):
        if not nums or len(nums) < 2:
            return False
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2
        if max(nums) > target:
            return False
        
        # 1D DP array: dp[j] = whether sum j can be formed
        dp = [False] * (target + 1)
        dp[0] = True  # Base case: sum 0 is always possible
        
        for num in nums:
            # Iterate from target down to num to avoid reusing the same element multiple times
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        
        return dp[target]

Key Notes #

• We update the array right-to-left to ensure each element is only considered once per iteration (no multiple selections of the same element).
• At the end, dp[target] directly tells us if a valid partition exists.

2. Modifying the Code to Return the Actual Subsets #

To return the two subsets instead of a boolean, we need to track the path of elements we select during backtracking. When we find a subset that sums to target, we can derive the second subset by removing those elements from the original list.

Modified Code with Subset Tracking #

class Solution(object):
    def canPartition(self, nums):
        if not nums or len(nums) < 2:
            return []
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return []
        target = total_sum // 2
        if max(nums) > target:
            return []
        
        nums.sort(reverse=True)
        # Call helper to find the subset that sums to target
        subset = self.helper(nums, 0, target, 0, [])
        if not subset:
            return []
        
        # Create the second subset by accounting for element frequencies
        from collections import defaultdict
        element_count = defaultdict(int)
        for num in nums:
            element_count[num] += 1
        for num in subset:
            element_count[num] -= 1
            if element_count[num] == 0:
                del element_count[num]
        
        subset2 = []
        for num, count in element_count.items():
            subset2.extend([num] * count)
        
        return [subset, subset2]
    
    def helper(self, nums, index, target, curr_sum, current_path):
        if curr_sum == target:
            return current_path.copy()  # Return a copy to avoid backtracking modifications
        for i in range(index, len(nums)):
            if curr_sum + nums[i] > target:
                continue
            # Add current element to path and recurse
            current_path.append(nums[i])
            result = self.helper(nums, i + 1, target, curr_sum + nums[i], current_path)
            if result:
                return result
            # Backtrack: remove element if it doesn't lead to a solution
            current_path.pop()
        return None

Explanation #

• The helper function now tracks current_path to record elements we've selected. When we hit the target sum, we return a copy of the path (to preserve it during backtracking).
• We use a frequency dictionary to handle duplicate elements correctly: we count occurrences in the original list, subtract the elements in the first subset, then build the second subset from the remaining counts.
• If no valid partition exists, the function returns an empty list.

内容的提问来源于stack exchange，提问作者coderWorld