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;
}

• AJNeufeld: "Can somebody help what I might be doing wrong." Code Review is for reviewing working code, looking for: security holes, hidden bugs, clarity, maintainability, inefficiencies, and scalability. It is not for assistance getting the code to work.
• Harry: @AJNeufeld My code works for small target sums, but for this case I'm getting TLE
• AJNeufeld: You'll should include the problem text in the body of your post. It is not clear what the "Target Sum array problem" exactly is.
• Harry: @AJNeufeld updated the post
• AJNeufeld: The exact problem text, with limits, and examples. Perhaps even a link to the target question as well (does not eliminate the need to embed the exact problem text with limits and examples in your post, as links do vanish over time, or may require logins to view). It does not seem to match Target Sum or Combination Sum or Two Sum or any other challenge I can see.

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.

• Harry: doesn't std::vector<std::optional<std::vector<int>>> memo serve that purpose. If memo[target_sum] which is std::optional<std::vector<int>> is initialized return that std::optional<std::vector<int>> else compute it and store it memo[target_sum]
• 1201ProgramAlarm: @Harry You have default constructed optional objects (which will have not have a value (std::nullopt). If the sum fails, you store std::nullopt in to the optional value, which is the same as a default constructed one.
• Harry: Thanks for correcting me. I used an std::map instead of std::vector for declaring memo type. It now works.