Solving subset sum with dynamic programming
Dynamic programming is a generic method of solving a problem instance by breaking it into smaller sub-instances and then combining the results to a result of the original instance. It differs from divide and conquer in that the sub-instances are overlapping and thus their results can be memoized and not computed again and again.
In this exercise, your task is to introduce yourself to dynamic programming and implement an algorithm that solves the subset sum problem with dynamic programming. To get started, you may take a look at the dynamic programming and subset sum pages in wikipedia.
Note that dynamic programming technique works well on subset sum problem instances in which the number of all possible subset sums is reasonable small (in the order of millions): even though a set s can have an enormous amount of subsets, many of these subsets can in fact sum up the same value. For instance, if s = {2, 5, 3, 4, 7, 8, 9, 10,....}, then there are at least four subsets summing to 24: {2, 5, 7, 10}, {2, 5, 8, 9}, {3, 4, 7, 10}, and {3, 4, 8, 9}. Dynamic programming exploits this fact by remembering, for instance, that there is a subset {2, 5, 7, 10} summing to the value 24 and does not need to explore the other subsets. Of course, one does not want to store all these subsets explicitly but with minimal amount of information (for instance, for the value 24 one only needs to remember that there is a subset summing to that value and that subset was obtained by adding 10 to another subset [summing up to the value 24 – 10 = 14]).

Use scala 3. Replace the ??? symbol with your solution, do not use external libraries.

Code:
package object subsetsumDynProg:
  
  /**
   * Solve the subset sum problem with dynamic programming.
   * Dynamic programming works in cases where the amount of sums that can be formed is
   * still reasonable (in the order of millions).
   */
  def solve(set: Set[Int], target: Int): Option[Set[Int]] = 
    ???
  end solve

 
  
  /*
   * The rest of the code includes the recursive backtracking search version
   * given in the course material.
   * This is only for reference, you don't need to use or modify it in any way.
   */
  /** Select an arbitrary element in s */
  def selectElementSimple(s: Set[Int], t: Int) =
    require(!s.isEmpty)
    s.head
  end selectElementSimple

  /** Select an element in s in a greedy way */
  def selectElementGreedy(s: Set[Int], t: Int) =
    require(!s.isEmpty)
    if t > 0 then s.max
    else s.min
  end selectElementGreedy

  /**
   * Solve the subset sum problem with recursion.
   * The argument function heuristics is a function that, when called with
   * a non-empty set s and value t, returns an element in s.
   */
  def solveBacktrackingSearch(set: Set[Int], target: Int, 
    elementSelector: (Set[Int], Int) => Int = selectElementSimple): Option[Set[Int]] =

    def inner(s: Set[Int], t: Int): Option[Set[Int]] =
      if t == 0 then
        // An empty set sums up to t when t = 0
        return Some(Set[Int]())
      else if s.isEmpty then
        // An empty set cannot sum up to t when t != 0
        return None
      else if s.filter(_ > 0).sum < t || s.filter(_ < 0).sum > t then
        // The positive (negative) number cannot add up (down) to t
        return None
      // Select one element in the set
      val e = elementSelector(s, t)
      val rest = s - e
      // Search for a solution without e
      val solNotIn = inner(rest, t)
      if solNotIn.nonEmpty then return solNotIn
      // Search for a solution with e
      val solIn = inner(rest, t - e)
      if solIn.nonEmpty then return Some(solIn.get + e)
      // No solution found here, backtrack
      return None
    end inner
    
    inner(set, target)
  end solveBacktrackingSearch