题目描述

本题与原题的唯一区别在于，本题的约束条件更低。

初始时，数组 $a$ 只包含数字 $1$。你可以进行若干次操作来改变数组。在每次操作中，你可以选择 $a$ 的一个子序列 $^{\dagger}$，并将该子序列所有元素的和作为一个新元素加入到 $a$ 中。

现在给定一个最终数组 $c$。请判断是否可以通过对初始数组 $a$ 进行若干次（可能为零次）操作后得到数组 $c$。

$^{\dagger}$ 如果序列 $b$ 可以通过从序列 $a$ 中删除若干（可能为零个，但不能全部）元素得到，则称 $b$ 是 $a$ 的一个子序列。换句话说，就是选择 $k$（$1 \leq k \leq |a|$）个不同的下标 $i_1, i_2, \dots, i_k$，并在 $a$ 的任意位置插入一个新元素，其值为 $a_{i_1} + a_{i_2} + \dots + a_{i_k}$。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示最终数组 $c$ 的元素个数。

每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $c_i$（$1 \leq c_i \leq 5000$），表示需要通过操作得到的最终数组 $c$。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

输出格式

对于每个测试用例，如果存在这样一系列操作可以得到数组 $c$，输出 "YES"（不含引号）；否则输出 "NO"（不含引号）。

你可以用任意大小写输出答案（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定答案）。

样例

6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1

YES
NO
YES
NO
YES
YES

样例说明

对于第一个测试用例，初始数组 $a$ 已经等于 $[1]$，因此答案为 "YES"。

对于第二个测试用例，无论进行多少次操作，$a$ 的大小至少为 $2$，且不会只包含元素 $2$，因此无法得到数组 $[2]$，答案为 "NO"。

对于第三个测试用例，可以按如下操作得到最终数组 $c$：

• 初始时，$a = [1]$。
• 选择子序列 $[1]$，插入 $1$，$a$ 变为 $[1, 1]$。
• 选择子序列 $[1, 1]$，插入 $1+1=2$，$a$ 变为 $[1, 2, 1]$。
• 选择子序列 $[1, 2]$，插入 $1+2=3$，$a$ 变为 $[1, 3, 2, 1]$。
• 选择子序列 $[1, 3, 1]$，插入 $1+3+1=5$，$a$ 变为 $[5, 1, 3, 2, 1]$（这就是我们需要得到的数组）。

由 ChatGPT 4.1 翻译

来源

Codeforces 1807G1，英文题名 Subsequence Addition (Easy Version)。