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, ,

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 ?

• 0

 » 18 months ago, # |   0 Solved :v
 » 5 weeks ago, # | ← Rev. 3 →   0 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); }