3 ms·
Can't subset sum like in TFA be solved by dynamic programming using a modified 0-1 knapsack? (modified to keep track of selected items)
by TacticalCoder 2y ago
Can't subset sum like in TFA be solved by dynamic programming using a modified 0-1 knapsack? (modified to keep track of selected items)
- JohnKemeny 2y agoYup, in time (and space) O(M • n), so with M = 1 million and let's say n = 1 million, it takes space 1 trillion. Given a byte per number, it takes a TB of memory, but is otherwise doable. Ps, you don't want to risk a running time of form O(Mn²).