Я работаю над следующей проблемой :
Учитывая набор неотрицательных различных целых чисел и значение m, определите, существует ли подмножество данного набора с суммой, кратной m.
Ввод: Первая строка ввода содержит целое число T, обозначающее количество тестовых случаев. Затем следуют тесты T. Первая строка каждого теста содержит целое число N и M, где N обозначает размер массива, а M - число, для которого мы должны проверить делимость. Вторая строка каждого теста содержит N целых чисел, разделенных пробелом, обозначающих элементы массива A [].
Вывод: Если существует подмножество, которое делится на M, выведите «1», иначе выведите «0».
Я пробовал рекурсивное решение:
#include <iostream>
#include<unordered_map>
using namespace std;
bool find_it(int a[],int &m,int n,int sum) {
if ((sum%m)==0 && sum>0)
return true;
if (n==0)
return false;
return find_it(a,m,n-1,sum) || find_it(a,m,n-1,sum-a[n-1]);
}
int main() {
int tc;
cin >> tc;
while (tc--) {
int n,m;
cin >> n >> m;
int a[n];
int sum = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
sum += a[i];
}
bool answer = find_it(a,m,n,sum);
cout << answer << "\n";
}
return 0;
}
Который работает нормально и принимается, но затем я попробовал нисходящий подход и получаю TLE («Превышено ограничение по времени»). Что я делаю не так в этой заметке?
#include <iostream>
#include<unordered_map>
using namespace std;
bool find_it(
int a[], int &m, int n, int sum,
unordered_map<int,unordered_map<int,bool>> &value,
unordered_map<int,unordered_map<int,bool>> &visited){
if ((sum%m)==0 && sum>0)
return true;
if(n==0)
return false;
if(visited[n][sum]==true)
return value[n][sum];
bool first = false,second = false;
first = find_it(a,m,n-1,su1m,value,visited);
if(sum<a[n-1])
{
second=false;
}
else
second = find_it(a,m,n-1,sum-a[n-1],value,visited);
visited[n][sum] = true;
value[n][sum] = first || second;
return value[n][sum];
}
int main() {
int tc;
cin >> tc;
while (tc--) {
int n,m;
cin >> n >> m;
int a[n];
int sum = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
sum+=a[i];
}
unordered_map<int,unordered_map<int,bool>> value;
unordered_map<int,unordered_map<int,bool>> visited;
cout << find_it(a,m,n,sum,value,visited) << "\n";
}
return 0;
}