Super weird test case: DP gets TLE but DFS gets AC


  • 0
    M

    this question is totally same as Subset Sum Problem
    since the number will not exceed 100 and there are less than 100 numbers, sum of numbers will be less than 10000
    time complexity of DP is O(n^3)

    but naive DPS gets AC, which complexity is O(2^n)
    and it takes only 55ms of python


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.