Leetcode Problem 494. Target Sum

494. Target Sum

Leetcode Solutions

Approach: Recursion with Memoization

  1. Define a recursive function calculate that takes the current index, the running sum, and the target sum as arguments.
  2. If the current index is equal to the length of the input array, check if the running sum is equal to the target sum. If so, return 1; otherwise, return 0.
  3. Check if the result for the current index and running sum is already in the memoization table. If it is, return the stored result.
  4. Recursively call calculate with the next index and the running sum plus the current number to explore the '+' option.
  5. Recursively call calculate with the next index and the running sum minus the current number to explore the '-' option.
  6. Store the sum of the results from steps 4 and 5 in the memoization table.
  7. Return the stored result.
  8. Initialize the memoization table and call calculate starting with index 0 and a running sum of 0.
UML Thumbnail

Approach: Brute Force

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...