Given a list of integers S and a target number k, write a function that returns true. If such a subset cannot be made, then return false.

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

Example

1 2 3

Input: S = [12, 1, 61, 5, 9, 2], k = 24, Output: true since [12, 9, 2, 1] sums up to 24.

Solution

This is the classical 0-1 Knapsack problem and we can apply into 2D (dp[n+1][k+1]) and then iterate each possibilities. Actually, if we want to show what kind of subset looks like, we can use backtracking.