Can anyone please let me know why this program is generating a std::bad_alloc error?
#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;
int sumf (vi vec) {
int sum=0;
for(int i:vec) sum+=i;
return sum;
}
void peek (vi l) {
for(int i:l) cout << i << " ";
cout << endl;
}
void solve (vi l, vi sub, int t, int i, int n) {
sub.push_back(l[i]);
if(sumf(sub)==t) {
peek(sub);
sub.pop_back();
return;
}
for(int ii=i;ii<n;ii++) solve(l,sub,t,ii,n);
}
int main () {
vi l = {2,3,6,7};
vi sub;
int t = 7;
solve(l,sub,t,0,l.size());
}
Your program reaches a very large recursion depth for the solve calls (about 30’000 nested calls to solve before it crashes on my machine), and each has its own copy of sub (because you pass it by value), and each copy of sub is one larger than its parent.
Eventually, the sum of the sizes of all copies of sub in the callstack gets so big that you run out of memory.
It’s possible that you intended the following:
#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;
int sumf (vi vec) {
int sum=0;
for(int i:vec) sum+=i;
return sum;
}
void peek (vi l) {
for(int i:l) cout << i << " ";
cout << endl;
}
void solve (vi& l, vi& sub, int t, int i, int n) {
sub.push_back(l[i]);
if(sumf(sub)==t) {
peek(sub);
sub.pop_back();
return;
}
for(int ii=i;ii<n;ii++) solve(l,sub,t,ii,n);
}
int main () {
vi l = {2,3,6,7};
vi sub;
int t = 7;
solve(l,sub,t,0,l.size());
}
though this still crashes, this time (I presume) due to a stackoverflow.
Exactly! I’m wondering why though would it go to such depths, since 7 is a very small target and should require very few levels to achieve? It doesn’t seem to make sense to me right now why does it have to go to such great depths.
Add