784. Check if Any Subsequence Equals Target Sum

Given an integer array nums and an integer target, return true if there exists any subsequence (including the empty subsequence, which has sum 0) whose elements sum to exactly target, otherwise return false. Elements may be negative. Implement recursively.

Input: An integer array and a target: "[a1,...], target".

Output: Return a boolean: true or false.

Examples

Input: [1,2,3], 3
Output: true
Explanation: {3} or {1,2} sum to 3.

Input: [1,2,3], 7
Output: false
Explanation: Max sum is 6 < 7.

Input: [1,-1,2,-2], 0
Output: true
Explanation: Empty subsequence has sum 0.

Constraints

• 1 <= nums.length <= 20
• -100 <= nums[i] <= 100
• -1000 <= target <= 1000

Asked by