集合里的乘法
题目描述
给定一个目标数T和一个整数集合S，判断是否存在S的一个非空子集，子集中的数相乘的积为T。
关于输入
输入为两行。
第一行为目标数T，和S中的元素个数N，以空格隔开。
第二行为S中的N个元素，以空格隔开。
其中 N <= 16。
关于输出
如果可以，则输出YES，否则输出NO。
例子输入
12 5 1 2 3 4 5
例子输出
YES
解题分析
这个算法的核心思想是使用深度优先搜索（DFS）遍历所有可能的子集，并计算它们的乘积。如果找到一个子集的乘积等于目标数，就返回YES，否则返回NO。
以下是该算法的详细步骤：
1. 首先，我们读取目标数T和集合S的元素。集合S的元素被存储在一个数组中，数组的索引从0开始。
2. 然后，我们调用深度优先搜索函数`dfs`，开始时的索引为0，乘积为1。这意味着我们从集合的第一个元素开始搜索，初始的乘积是1（因为任何数乘以1都等于它自己）。
3. 在`dfs`函数中，我们首先检查是否已经找到了解决方案（`flag`是否为1）或者当前乘积是否已经超过了目标数T。如果是的话，我们就直接返回，不再继续搜索。这是一种剪枝策略，可以避免无效的搜索，提高算法的效率。
4. 然后，我们检查当前的乘积是否等于目标数，如果是的话，我们就设置`flag`为1并返回。这表示我们已经找到了一个满足条件的子集。
5. 如果当前的索引已经达到了集合的大小，这意味着我们已经遍历了所有的元素，但还没有找到满足条件的子集，所以我们就返回。
6. 否则，我们对当前索引的元素有两种选择：一是选择它（将它乘入当前的乘积），二是不选择它（保持当前的乘积不变）。我们对这两种选择都进行搜索。这是深度优先搜索的核心步骤，通过递归调用`dfs`函数，我们可以遍历所有可能的子集。
7. 在主函数中，如果`flag`为1，说明我们找到了一个解决方案，输出YES。否则，输出NO。
这个算法的时间复杂度是O(2^n)，其中n是集合的大小。因为对于集合中的每一个元素，我们都有两种选择：选择它或者不选择它。所以总共有2^n种可能的子集。由于题目中给出集合的大小不超过16，所以这个算法在时间上是可行的。
代码实现
#include <stdio.h>
int N;
long long T, S[16];
char flag;
void dfs(int index, long long product) {
if (flag || product > T) return;
if (product == T) {
flag = 1;
return;
}
if (index == N) return;
dfs(index + 1, product * S[index]);
dfs(index + 1, product);
}
int main() {
scanf("%lld %d", &T, &N);
for (int i = 0; i < N; i++) {
scanf("%lld", &S[i]);
}
dfs(0, 1);
if (flag) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
