题目描述

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

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

输入格式

第一行输入一个整数 $n$ ，表示数组的长度。

第二行输入一个长度为 $n$ 的数组 $nums$ 。

第三行输入一个整数 $target$ 。

输出格式

从 $nums$ 中找出并输出总和为 $target$ 的元素组合的个数。

3
1 2 3
4

7

1
9
3

0

数据范围

$1 \leq n \leq 200$

$1 \leq nums[i] \leq 1000$

$nums$ 中所有元素 互不相同

$1 \leq target\leq 1000$

样例1解释

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