Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

_FAHA_'s blog

By _FAHA_, history, 18 months ago, In English,

Just like LOJ 1127, in 1235 I want to use Meet in the middle . Here , as we can take any coin for max two times. So, we can pick a coin in three ways .

For n coins the sub array sum will be of 3^n elements . So we can split it in two 3^(n/2) sized arrays .

But how 3^(n/2) combinations of sum can be generated ?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved :v

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
void generate_(vll &v, ll pos, ll sum, ll n)
{
    if (pos >= n)
    {
        v.push_back(sum);
        return;
    }
    generate_(v, pos+1, sum, n);
    generate_(v, pos+1, sum+arr[pos], n);
    generate_(v, pos+1, sum+arr[pos]*2, n);
}