CSES problem,apple division

https://cses.fi/problemset/task/1623 this is link to problem.
somebody please help me understand this code here,please!

#include <bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
const lli mod = 1e9 + 7;

int main()
lli n, total=0, ans=INT_MAX;
cin >> n;
li arr[n];
for(lli i = 0; i < n; i++) {
cin >> arr[i];
total += arr[i];
for(lli i = 0; i < 1<<n; i++) {
lli s = 0;
for(lli j = 0; j < n; j++) {
if(i & 1<<j) s += arr[j];
lli curr = abs((total-s)-s);
ans = min(ans, curr);
cout << ans;
return 0;

1 Like

It literally just tries all possible subsets and takes the minimum absolute difference (note that the second group is, by default, anything that isn’t in the first group).


thanku so much for taking time, i m just not getting the line(i & 1<<j) why is it checking the jth bit of i.


it was amazing, really amazing thing i learnt today ! thanku so much !

learnt a new thing thank you.
but i have only one query
this solution is possible when n<=32 right? because if n>32 it can’t be represented in the bit representation right? coorect me if i am wrong
i am trying to learn bit manipulation

Mostly correct (although you could use 64-bit long long too - that’s the real upper limit). And looping all other masks would have other problems too with that many values, 2^{32} or 2^{64} operations would definitely TLE.


Please explain that solution to me.

ohh okay thank you for the help.

you can also use a back tracking approach for this problem

you can use bits to solve this problem by looping over all the possible combinations as described in other replies but here i found a recursive and dynamic programming solution