• Difficulty: Medium
• Patterns:
  • Dynamic Programming

---

Problem Definition

Given a dictionary of words pointing to positive numbers and a number $n$, return all combinations of the words that add up to the number $n$.

---

Example

({"foo": 2, "bar": 3, "baz": 5}, 10) -> [foo*5, foo*2 + bar*2, foo + bar + baz, baz*2]

---

Brute Force Solution

For each word $k$ with weight $v$ less than $n$, we'll subtract its value from $n$ and recursively get all words that sum to $n - v$.

def find_dict_sums(d, n):
    to_return = []
    for k, v in d.items():
        if v < n:
            for result in find_dict_sums(d, n - v):
                if len(result):
                    to_return.append(result + [k])
        elif v == n:
            to_return.append([k])
    return to_return

---

Brute Force Solution Complexity

Let $m = $ len(d).

In the worst case, each key has a value of 1, which means each solution will be of length $n$. This implies that in the worst case, we might make $m$ recursive calls at the top and then $m-1$ recursive calls in each nested call with a depth of $n$ nested recursive calls, implying a runtime complexity of $O(m^n)$.

Since we are creating $n$ nested stack frames and might create a to_return of size $m$, the auxiliary space complexity should be $O(m \cdot n)$.

---

Dynamic Programming Solution

We can improve the runtime by using a dynamic programming approach.

def find_dict_sums(d, n):
    q = []
    result = []
    terminal_targets = set()
    for k, v in d.items():
        new_target = n - v
        if new_target == 0:
            result.append((k,))
        elif new_target > 0:
            q.append((new_target, (k,)))
    while q:
        curr_target, seq = q.pop()
        target_terminal = True
        for k, v in d.items():
            new_target = curr_target - v
            if new_target == 0:
                result.append(seq + (k,))
                target_terminal = False
            elif new_target > 0 and new_target not in terminal_targets:
                q.append((new_target, seq + (k,)))
                target_terminal = False
        if target_terminal:
            terminal_targets.add(curr_target)
    return result