Golang中分区相等的子集和超出时间限制问题

本篇文章向大家介绍《Golang中分区相等的子集和超出时间限制问题》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

我正在运行这个程序来使用带有记忆功能的 dp 来解决分区总和问题，但这超出了时间限制

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. 当您使用递归时，它会使所有内存都在堆栈中分配（其大小是有限的），因此如果您有很多函数调用，您最终会遇到堆栈溢出错误。
2. 看起来您正在尝试所有可能的组合，这需要 O(n!)。现代 CPU 每秒可以处理大约 10^9 次操作，因此如果 n > 13，您将永远计算它。

最好考虑一下其他解决方案。但是这个问题是 NP full 的，最好的解决方案似乎是 O(2^n) 复杂度，所以无论如何你可能有太大的测试集。 此外，减少相同的匹配数字（成对）似乎是一个好主意，因为这种复杂性即使是 n 的小幅降级也会带来不错的指数时间胜利

本篇关于《Golang中分区相等的子集和超出时间限制问题》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！