Count Subsets with Sum K

Given a positive integer array arr and positive target k, count index subsets whose sum is exactly k. Each position can be selected at most once. Equal values…

Given a positive integer array arr and positive target k, count index subsets whose sum is exactly k. Each position can be selected at most once. Equal values at different positions are distinct choices. Return the count modulo 1,000,000,007.

- 1 <= n <= 100; 1 <= arr[i] <= 1000; 1 <= k <= 1000. - Zero values, zero target and empty public inputs are excluded. - Visualization accepts at most 6 items and k at most 10; larger valid inputs are coding-only. Impossible sums are resolved by the indexed-choice DP, not a signed-assignment parity check.

Example 1: input values = [2,2], target = 2; output 2. Either of the two indexed positions can supply the required 2.

Example 2: input values = [2,3,5], target = 5; output 2. Select positions 0 and 1 for 2 + 3, or position 2 alone for 5. These are the only two subsets totaling 5.

Example 3: input values = [2,4], target = 3; output 0. The possible subset sums are 0, 2, 4 and 6; none equals 3.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.