Golang实现Partition Equal Subset Sum超时问题排查求助

我用带记忆化的动态规划实现分割等和子集问题，提交后超时，状态如下：

Time Submitted Status Runtime Memory Language
08/30/2022 23:49 Time Limit Exceeded N/A N/A golang

我的DP实现代码如下：

func canPartition(nums []int) bool {
    // sum & divide by 2, mod should be 0
    sum := 0 
    fsum := 0
    
    if len(nums) > 0 {
        for i := range nums {
            sum = sum + nums[i]
        }
    } else {
        return false
    }
    
    if sum % 2 == 0 {
        fsum = sum/2 
    } else {
        return false
    }
    
    check := make(map[int]map[int]bool, 0)
    // initial subset of sum is 0
    check = map[int]map[int]bool{}
    return recurse(nums, 0, 0, fsum, check)
}

func recurse(nums []int, index, sum, total int, check map[int]map[int]bool) bool {
    if sum > total || index > len(nums)-1 {
        return false
    }

    if sum == total {
        return true
    }
    
    if _, ok := check[sum][index]; ok {
        return check[sum][index]
    }
    
    check[sum] = map[int]bool{index:recurse(nums, index+1, sum+nums[index], total, check) || recurse(nums, index+1, sum, total, check)}
    return check[sum][index]
}

请问我哪里考虑不周？

超时原因 #

1. 嵌套Map的性能损耗：你用map[int]map[int]bool做记忆化缓存，Go里嵌套Map的存取操作本身就有较高的时间开销，递归调用频繁时，这部分损耗会被放大，直接拖慢程序。
2. 记忆化逻辑错误：每次执行check[sum] = map[int]bool{index: ...}时，会直接覆盖check[sum]对应的整个内层Map，导致之前存储的其他index的缓存数据全部丢失。后续递归遇到相同sum但不同index的情况时，还是会重复计算，等于白做了记忆化。
3. 递归的额外开销：递归本身会产生函数调用栈的开销，对于大规模输入，栈开销加上重复计算（因为缓存失效），很容易触发超时。

改进方案 #

方案1：优化记忆化缓存结构 #

把嵌套Map换成二维数组，因为sum的最大值是总和的一半（target），index的最大值是数组长度，两者范围都是确定的，数组的存取速度远快于Map：

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }
    target := sum / 2
    // dp[i][j]：考虑前i个元素，能否凑出和为j；-1=未计算，0=不能，1=能
    dp := make([][]int, len(nums))
    for i := range dp {
        dp[i] = make([]int, target+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }
    return recurse(nums, 0, 0, target, dp)
}

func recurse(nums []int, index, currentSum, target int, dp [][]int) bool {
    if currentSum == target {
        return true
    }
    if index >= len(nums) || currentSum > target {
        return false
    }
    if dp[index][currentSum] != -1 {
        return dp[index][currentSum] == 1
    }
    // 选或不选当前元素
    res := recurse(nums, index+1, currentSum+nums[index], target, dp) || recurse(nums, index+1, currentSum, target, dp)
    dp[index][currentSum] = map[bool]int{true:1, false:0}[res]
    return res
}

方案2：改用迭代式DP（最优解） #

递归的开销可以完全避免，用0-1背包的迭代思路实现，时间复杂度O(n*target)，空间还能进一步优化：

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }
    target := sum / 2
    // dp[j]：能否凑出和为j
    dp := make([]bool, target+1)
    dp[0] = true // 和为0的情况默认成立
    for _, num := range nums {
        // 倒序遍历，防止重复选取同一元素
        for j := target; j >= num; j-- {
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}

这个一维迭代版本把空间复杂度从O(n*target)降到了O(target)，时间效率也最高，能轻松通过大规模测试用例。

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