This Problem was asked in Online Assesment round for internship opportunity for Salesforce.

A number is called smart iff it's digits can be partitioned into two sets, such that sum of both sets is equal. Forr example 52139 is a smart number since 5 + 2+ 3= 9 + 1, but 3288 isn't a smart number. Given a range [a , b], find the count of smart number within the range.

constraint: a <= b <= 2 x 10 ^ 5

Example 1 :
Input : [1,100]
Output: 9
Explanation : 11,22, 33, 44,55,66,77,88,99 are the only smart numbers in this range.

Example 2:
Input: [1,1000]
Output: 135

My solution :
Idea : Using 0-1 Knapsack DP we check whether half the sum of is ahievable.
Code :

bool check(int a){
    vector<int> v; int sum = 0,x=a;
    while(a) v.PB(a%10),sum+=(a%10),a/=10;
    if(sum&1) return false; sum>>=1;
    vector<bool> possible_sums(sum+2,0);
    possible_sums[0] = 1;
    for(int i = v.size()-1; i >= 0 ; i--){
        for(int j = sum+1; j>= v[i] ; --j ){
         possible_sums[j] = (possible_sums[j] or possible_sums[j-v[i]]);   
        }
    }
    return possible_sums[sum];
}


void smart_numbers(int a, int b)
{
    int ans = 0;
    for(int i =a ; i <= b ; i++){
        ans += check(i);
    }
    cout<<ans;
}