组合总和的方案数

题目描述

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

题目数据保证答案符合 32 位整数范围。

请注意，顺序不同的序列被视作不同的组合。

输入格式

第一行包含两个整数 $n$ 和 $target$，分别表示数组的长度和目标值。

第二行包含 $n$ 个整数，表示数组 nums 中的元素。

输出格式

输出一行一个整数，表示总和为 target 的元素组合的个数。

输入输出样例 #1

输入 #1

3 4
1 2 3

输出 #1

7

样例 #1 解释

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。

输入输出样例 #2

输入 #2

1 3
9

输出 #2

0

样例 #2 解释

数组中没有数能组成目标值 3，因此返回 0。

数据范围

对于 $100\%$ 的数据，保证 $1 \leq n \leq 200$，$1 \leq nums[i] \leq 1000$，$nums$ 中的所有元素互不相同，$1 \leq target \leq 1000$。