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.