网格-递归作业集合里的乘法

描述
给定整数集合S和一个目标数T，判断是否可以从S中挑选一个非空子集，子集中的数相乘的乘积为T。
关于输入
输入为两行。第一行为目标数T和S中的元素个数N，以空格隔开。第二行为S中的N个元素，以空格隔开。其中 N <= 16。
关于输出
如果可以，则输出YES，否则输出NO。
例子输入
Sample Input 1: 12 5 1 2 3 4 5 Sample Input 2: 33 5 4 2 8 7 5
例子输出
Sample Output 1: YES Sample Output 2: NO

代码：

 1 //集合里的乘法 
 2 // 3 //2019-11-11 
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 int a[20];
 8 //涉及到除法就要考虑0的特判 
 9 bool mult(int num, int k, int n){ //试到第k个数.要用乘法凑出num, 一共n个数 
10     if(num==a[k]) return true;  
11     if(a[k]==0) return false; //一定要注意 
12     if(k+1<=n){
13         if(num%a[k]==0){
14             if(mult(num/a[k],k+1,n)) //取当前数 
15                 return true;
16             else
17                 return mult(num,k+1,n); //不取当前数 
18         }
19         else
20             return mult(num,k+1,n); //不取当前数         
21     }        
22     return false;
23 } 
24 int main(){
25     int t, n;
26     cin>>t>>n;
27     for(int i = 1; i <= n; i++)
28         cin>>a[i];
29     if(mult(t,1,n))
30         cout<<"YES"<<endl;
31     else
32         cout<<"NO"<<endl; 
33     return 0;
34 }

备注：

感觉自己这个回溯写的挺乱的。关键在于拆分子问题。用递归来暴力枚举每一个书取或不取。但因为我用的是除法，一定要注意除数不能为0，但如果用直接暴力乘的话就没有这个问题。

我的代码写的太差了，补一个作业范例，思路就超级清晰：

 1 #include <iostream>
 2 using namespace std;
 3 int e[50],found=0,t,card;//数组 e 记录集合中的元素，found 记录是否已经找到子集
 4 void attempt(int i, int k)
 5 {
 6      if (found || i>card) return;
 7      if (k==t)
 8      {
 9          cout << "YES"; found=1; return;
10      }
11      attempt(i+1, k);//子集中不包含这个数
12      attempt(i+1, k*e[i]);//子集中包含这个数
13 }
14 int main()
15 {
16      cin >> t >> card;
17      for (int i=1; i<=card; i++) cin >> e[i];
18      attempt(1,1);
19      if (!found) cout << "NO";//如果没找到就输出 NO
20      return 0;
21 }

网格-递归作业 集合里的乘法

网格-递归作业集合里的乘法