Target Sum array using Dynamic Programming

Question

I'm learning Dynamic Programming and trying to solve this Target Sum array problem. I've to find an array of integers that sums to a given target sum using the integers of given input array. I've used memoization technique but still getting TLE. Can somebody help what I might be doing wrong. This is my code:

#include <iostream> #include <vector> #include <optional> std::optional<std::vector<int>> can_sum(const long long target_sum, const std::vector<int>& nums, std::vector<std::optional<std::vector<int>>>& memo) { if (target_sum == 0) return std::vector<int>(); else if (target_sum < 0) return std::nullopt; else if (memo[target_sum]) return memo[target_sum]; for (const auto val : nums) { std::optional<std::vector<int>> arr = can_sum(target_sum - val, nums, memo); if (arr) { arr.value().push_back(val); memo[target_sum] = arr; return arr; } } memo[target_sum] = std::nullopt; return std::nullopt; } int main() { const long long target_sum = 300LL; const std::vector<int> nums { 7, 14 }; std::vector<std::optional<std::vector<int>>> memo(target_sum + 1); std::optional<std::vector<int>> arr = can_sum(target_sum, nums, memo); if (arr) { for (const auto val : arr.value()) std::cout << val << ", "; std::cout << std::endl; } else std::cout << "null" << std::endl; } 

Answer 1

In your memoization you cannot distinguish between target sums that have not been evaluated, and ones that you have evaluated but have no solution. This results in re-running these unsuccessful possibilities.

You should add some way to tell these two cases apart: Either use an empty vector to indicate that there is no viable sum, or use a class that stores the vector and has a couple of flags, one to indicate that the cached value is valid (has already been computed) and the other if the solution has been computed and is not possible.