Answer Happy

2. Consider the following problem and answer questions a) to d). Given a set of k positive integers {a₁, a2, ..., ak} that add up to N. Note that, there might 3 1 ≤i # j ≤ k such that a₁ = a;. Is there a subset B C {1,2,..., k} such that the follow equation is satisfied? = Σ₁6 ai a₁ = c) d) ¡EB iE{1,2,...,k}\B a) If N is an odd number, what do we know about the problem? b) From now on, N is an even number. Try to create a recursive function b(i, j) that represents the Boolean value whether there is a subset in {a₁, a2, ..., a;} that add up to j. How to create a memo to record the value of each b(i, j)? Describe in detail. How to use to memo to find the solution to the problem? What is the running time of this dynamic programming algorithm?