组合总和 Ⅳ

题目描述

给你一个由 不同 正整数组成的数组，数组长度为 n，以及一个目标整数 target。请你从中找出并返回总和为 target 的元素组合的个数。

注意：顺序不同的序列被视为不同的组合。例如 (1,2) 和 (2,1) 是两个不同的组合。

题目数据保证答案在 32 位有符号整数范围内。

---

输入格式

• 第一行包含两个整数 n 和 target（$1 \le n \le 200$, $1 \le \text{target} \le 1000$）。
• 第二行包含 n 个互不相同的正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 1000$）。

---

输出格式

• 输出一个整数，表示能组成目标值 target 的组合总数。

---

示例

示例 1

输入：

3 4
1 2 3

输出：

7

解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

共 7 种。

---

示例 2

输入：

1 3
9

输出：

0

解释：
无法用 9 组合成总和为 3。

---

提示

• $1 \le n \le 200$
• $1 \le a_i \le 1000$，且所有 $a_i$ 互不相同
• $1 \le \text{target} \le 1000$