1
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • \$\begingroup\$ "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. \$\endgroup\$
    – AJNeufeld
    Commented Oct 14, 2021 at 15:20
  • \$\begingroup\$ @AJNeufeld My code works for small target sums, but for this case I'm getting TLE \$\endgroup\$
    – Harry
    Commented Oct 14, 2021 at 15:25
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – AJNeufeld
    Commented Oct 14, 2021 at 15:27
  • \$\begingroup\$ @AJNeufeld updated the post \$\endgroup\$
    – Harry
    Commented Oct 14, 2021 at 15:32
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – AJNeufeld
    Commented Oct 14, 2021 at 15:39

1 Answer 1

3
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.