# Ruby Naive Solution TLE and Iterative Hash Map AC Solution

• 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
``````

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