Bob's Mother
For Christmas, Bob's mother tells him that he can keep his presents only if he solves her problem. His mother picks a number \(N\) and a sequence of \(L\) distinct positive integers. Bob's task is to sum up some of those numbers (a number can be used at most one time) to result in his mother's chosen number \(N\). However, sometimes his mother is sneaky and decides to choose a sequence of numbers such that there is no possible way to choose numbers that sum up to \(N\). Help Bob get his Christmas presents!
Constraints
\(1 \le N \le 10^9\)
\(1 \le a_i \le 10^6\), where \(a_i\) is a value from the sequence provided by Bob's mother
Subtask 1 [20%]
\(1 \le L \le 5\)
Subtask 2 [80%]
\(1 \le L \le 20\)
Input Specification
The first line will contain the integer \(N\), the number chosen by Bob's mother.
The second line will contain \(L\), the number of values provided by Bob's mother.
The third line will contain \(L\) positive integers separated by a space (this is the sequence provided by Bob's mom).
Output Specification
If it is possible to choose numbers that sum up to \(N\), output I can do it!. Otherwise, output Mom, you tricked me!.
Sample Input 1
10
4
1 5 3 6Sample Output 1
I can do it!Sample Explanation 1
1+3+6=10. Therefore, this is a valid sequence.
Sample Input 2
16
5
1 3 5 4 2Sample Output 2
Mom, you tricked me!Sample Explanation 2
No possible sum of these numbers can equal 16.
Comments
this is literally dp why is it listed as implementation
you dont even need dp
Intended solution was to iterate through subsets using recursion/using bitmasks: USACO Guide.
Your solution using bitmasks also works here but will most likely TLE under higher values of \(a_i\)!