**Problem :**CodeChef: Practical coding for everyone
Difficulty : easy
Topics: Bit manipulation , Brute force
Explanation :
For every potential problem set (which can be conveniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most difficult and the easiest problems in linear time, iterating over the problems that we included in our current set/bitmask. If this problem set can be used, we increase the answer by one.
Complexity of this solution is O(2^n·n).
Code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
long int i, j, x, l, r, n, m, mx, mn, sum, val, ans, a[100001];
while (cin >> n >> l >> r >> x) {
for (i = 0; i < n; i++) {
cin >> a[i];
} ans = 0;
for (i = 0; i < (1 << n); i++) {
mx = -1; mn = 1000000;
sum = 0;
for (j = 0; j < n; j++) {
if (i & (1 << j)) // Check if the i-th bit is set or not
{ sum += a[j]; mx = max(mx, a[j]);
mn = min(mn, a[j]);
}
}
if (l <= sum && sum <= r && (mx - mn) >= x) ans++; } cout << ans << endl;
}
return 0;
}