# Help needed understanding memoization behavior

While following a tutorial on memoization, I encountered this strange case where the memoized function is slightly slower than the brute force version in the worst case. I'm assuming my implementation is wrong (the tutorial was in Javascript), but I can't see where. Any help would be greatly appreciated.

func howSum(_ targetSum: Int, _ numbers: [Int]) -> [Int]? {
if targetSum == 0 { return [] }
if targetSum < 0 { return nil }

for num in numbers {
let remainder = targetSum - num
if var results = howSum(remainder, numbers) {
results.append(num)
return results
}
}
return nil
}

func howSum(_ targetSum: Int, _ addends: [Int])-> [Int]? {
var memo: [Int: [Int]?] = [:]
func sum(_ target: Int, _ numbers: [Int]) -> [Int]? {
if let early = memo[target] { return early }
if target == 0 { return [] }
if target < 0 { return nil }

for num in numbers {
let remainder = target - num
if var results = sum(remainder, numbers) {
results.append(num)
memo[target] = results
return results
}
}
memo[target] = nil
return nil
}
}

print(String(describing: howSum(7, [2, 3])))       //[3, 2, 2]
print(String(describing: howSum(7, [5, 3, 4, 7]))) //[4, 3]
print(String(describing: howSum(7, [2, 4])))       //nil
print(String(describing: howSum(8, [2, 3, 5])))    //[2, 2, 2, 2]
print(String(describing: howSum(300, [7, 14])))    //nil

I believe the issue is that when you write memo[target] = nil you are not actually storing the value Optional<[Int]>.none into the dictionary, but instead you are clearing the stored value for that key from the dictionary.

Thus, your code never actually memoizes â€śwe already proved this sum is unreachableâ€ť, and so it attempts to recompute it every time.

Change that line to memo[target] = .some(nil) and I think itâ€™ll work better.

â€˘ â€˘ â€˘

But really, the dictionary doesnâ€™t need to store arrays at all. It can simply store the last number it saw that made the sum equal the target. Then at the end when you want to generate an array, you traverse the dictionary by repeatedly subtracting from the target.

Something like this, which I also made generic:

_ targetSum: T,
) -> [T]?
where S.Element == T, T: Comparable, T: Hashable
{
var memo: [T: T?] = [:]

func lastAddendForTarget(_ target: T) -> T? {
if let early = memo[target] { return early }
if target == .zero { return .zero }
if target < .zero { return nil }

for n in addends where n <= target {
if lastAddendForTarget(target - n) != nil {
memo[target] = n
return n
}
}

memo[target] = .some(nil)
return nil
}

return nil
}

var result: [T] = []
var sum = targetSum

while let x = lastAddendForTarget(sum), x != .zero {
result.append(x)
sum -= x
}

return result
}

Note that my version returns an array with the elements in the opposite order from yours. If you prefer the original order, you can call reverse() on the result before returning it.

2 Likes

Thank you so much for that explanation and for taking the time to respond.