子集求和

题目背景

本题旨在探讨一种基本的递归回溯技术。理解这种模式对于解决许多涉及在选择空间中进行搜索的问题至关重要。

题目描述

给定一个整数数组，判断是否可能从中选择一组整数，使得这组整数的和等于给定的目标值。这是一个经典的递归回溯问题。一旦你理解了这个问题中的递归回溯策略，你就可以将相同的模式应用于许多问题，以搜索选择空间。我们约定不查看整个数组，而是考虑从 start 索引开始到数组末尾的部分。调用者可以通过将 start 设为 $0$ 来指定整个数组。不需要循环——递归调用会沿着数组向下推进。

输入格式

输入以如下格式从标准输入中给出。

start [数组元素] target

输出格式

输出以如下格式输出到标准输出中。

true 或 false

样例

0 [2 4 8] 10

true

0 [2 4 8] 14

true

0 [2 4 8] 9

false

样例解释

对于第一个样例，从数组 [2 4 8] 中选择 $2$ 和 $8$ 它们的和为 $10$，与目标值匹配。 对于第二个样例，从数组 [2 4 8] 中选择 $2$、$4$ 和 $8$ 它们的和为 $14$，与目标值匹配。 对于第三个样例，从数组 [2 4 8] 中无法组合出和为 $9$ 的数字。

数据范围

每个测试用例的时间限制为 1 秒，内存限制为 1024 KiB。