# Target Sum array using Dynamic Programming

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

• "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. Oct 14, 2021 at 15:20
• @AJNeufeld My code works for small target sums, but for this case I'm getting TLE Oct 14, 2021 at 15:25
• 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. Oct 14, 2021 at 15:27
• @AJNeufeld updated the post Oct 14, 2021 at 15:32
• 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. Oct 14, 2021 at 15:39

• 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] Oct 14, 2021 at 15:49
• @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. Oct 14, 2021 at 15:52
• Thanks for correcting me. I used an std::map instead of std::vector for declaring memo type. It now works. Oct 14, 2021 at 16:06