One Pager Cheat Sheet

• This article covers the Target Sum problem, which is similar to the 0-1 Knapsack Problem but requires deciding whether to add or subtract an item, before progressing to the more efficient dynamic programming solutions.
• The brute force solution of this problem is to explore every possibility using a backtracking algorithm.
• Although the server response time is acceptable at 377ms, there is still room for improvement.
• We can optimize our problem solving by using memoization and an offset of +1000 to account for negative values for better runtime performance.
• My score of 68.82th percentile is neither great nor terrible.
• Dynamic programming enables us to efficiently find the number of ways to reach a target sum S by considering only reachable target sums at each iteration.
• The use of an array with continue statement and a HashMap data structure each provide different ways of optimizing the solution, with the latter being theoretically faster but slower in practice.
• We can simplify our problem and significantly improve runtime performance by turning it into a 0-1 Knapsack Problem.
• Find the number of ways to gather a subset of nums such that its sum is equal to (target + sum(nums)) / 2, with the additional check that target + sum(nums) is divisible by 2.
• The final solution in code looks like this: number of ways to attain S without V minus number of ways to attain S-V with V, to determine the value in the same column for 1 row above, in the dynamic programming table.
• By optimizing our solution and caching it with memoization, we were able to reduce our runtime from 377ms to 1ms, an incredibly significant improvement.