Help needed understanding memoization behavior

Using Swift
#1

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
    }
    return sum(targetSum, addends)
}

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
#2

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:

func howSum<T: AdditiveArithmetic, S: Sequence>(
  _ targetSum: T,
  _ addends: S
) -> [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
  }
  
  if lastAddendForTarget(targetSum) == 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
#3

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

Terms of Service

Privacy Policy

Cookie Policy