Ruby Naive Solution TLE and Iterative Hash Map AC Solution


  • 0
    R

    Naive/brute force solution:

    Loop through all values, checking if they have met the target. Increment number of combinations that add to target if the value is equal to the target. Drop all values which are greater than or equal to target, as they are no longer valid. Add all values in nums to each remaining value, creating a new array consisting of the sums of all combinations that could still be valid. Continue until you have checked all possible combinations (in other words until the new array is empty because there are no remaining valid possible combinations).

    def combination_sum4(nums, target)
        count = 0
        temp_values = nums
        
        while(!temp_values.empty?) do  
            temp_values = temp_values.each_with_object([]) do |val, array|
               if val >= target
                 count += 1 if val == target
               else
                 nums.each { |num| array << num + val } 
               end
            end
        end
        count
    end
    

    Hash Map solution:
    We do a lot of repeated calculations with the first approach. Instead we can use a hash map to group our running combination sums together.

    def combination_sum4(nums, target)
        count = 0
        counts_hash = nums.each_with_object(Hash.new(0)) { |num, hash| hash[num] += 1 }
        
        while(!counts_hash.empty?) do  
            counts_hash = counts_hash.each_with_object(Hash.new(0)) do |(key, value), hash|
               if key >= target
                 count += value if key == target
               else
                 nums.each { |num| hash[num + key] += value } 
               end
            end
        end
        count
    end
    

Log in to reply
 

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