Target Sum

Medium

Given an array nums and an integer target k, assign a + or - to each number and count the assignments whose sum equals k.

Example 1

Input:  nums = [1,1,1,1,1], k = 3
Output: 5

Example 2

Input:  nums = [1], k = 1
Output: 1

Constraints

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• -1000 <= k <= 1000