Ruby DP with tabulation is getting TLE


  • 0
    C
    def has_subset_of_sum(sum, nums)
        subset_sum_matrix = Array.new(sum+1) { Array.new(nums.size+1) }
        for i in 1..sum do
            subset_sum_matrix[i][0] = 0
        end
        
        for i in 0..nums.size do
            subset_sum_matrix[0][i] = 1
        end
        
        for i in 1..sum do
            for j in 1..nums.size do
                
                if i >= nums[j-1] && subset_sum_matrix[i][j-1] == 0
                    subset_sum_matrix[i][j] = subset_sum_matrix[i-nums[j-1]][j-1]    
                else
                    subset_sum_matrix[i][j] = subset_sum_matrix[i][j-1]    
                end
            end
        end
        return subset_sum_matrix[sum][nums.size] == 1
    end
    
    def can_partition(nums)
        sum = 0
        nums.each do |num|
            sum+=num
        end
        return true if sum == 0
        return false if sum%2!=0
        
        sum/=2
        has_subset_of_sum(sum, nums)
    end
    

  • 0

    @chaitu14388 This is just fixed. Your Ruby solution should get Accepted now.


  • 0
    C

    @1337c0d3r thank you


Log in to reply
 

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