### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### PREREQUISITES

Dynamic Programming

### PROBLEM

You are given a set of **N** positive integers **A _{1}, A_{2} …, A_{N}**. You wish to find a special subset of this set such that

- The numbers in the set have
**mutually exclusive set of digits** - The
**sum of the numbers is maximum among all such sets** - For sets with the same sum, the
**cardinality**of the subset should be**maximum**

You have to print the cardinality of such a maximum sum special subset of the set given to you.

### EXPLANATION

There are **2 ^{N}** subsets possible for a set of

**N**elements.

Of course, in this problem, most of those **2 ^{N}** sets cannot be considered. This is because of the constraint that the numbers in the subset must have mutually exclusive set of digits.

In fact, a set will never have more than 10 numbers. Although, considering all sets of cardinality less than or equal to 10 is also impossible because there may simply be too many.

The key insight in this problem is that if we have two numbers made off the same set of digits, then we are always interested in the larger one. Hence, we never really have to consider more than **2 ^{10}** different numbers - since there are only 10 digits.

Of course, a set of digits can be represented by a bit set of 10 bits. Thus, **we store the largest given number for each bit set**.

We know that two bit sets can be **combined** if they don’t have a **set bit** for the **same digit**. This can be tested by a **bitwise-and** operation. If two bit sets can be combined, we will update the **combined bit-set** with the **larger sum**.

Just like the dynamic programming formulation for **0-1 knapsack** we can maintain the largest sum for each bit set as follows

SUM_{[1 .. 1024]}= {0} for i = 1 to N b = bitset for A_{i}for m = 0 to 1024 if (m & b) = 0 SUM_{m+b}= max(SUM_{m+b}, SUM_{m}+ SUM_{b})

The above accomplishes finding the maximum sums for each bit set (with combined numbers) in **O(N * 2 ^{10})** time.

This is sufficient to solve the problem. This approach is used in the setter’s as well as tester’s code.

There is an alternate way to solve the problem though that is slightly faster for **N ≥ 50**. It utilises the fact that **we don’t need to consider the numbers one by one**.

The dynamic programming formulation works just as well if we consider them all at once. If we resolve the final answers for the bit sets from **smaller ones** to **larger ones**, then we ensure that the dynamic program above works in the following code.

Consider the pseudo-code below

SUM_{[1 .. 1024]}= {0} //mark 1 for i = 1 to N b = bitset for A_{i}SUM_{b}= max(SUM_{b},A_{i}) //mark 2 for m = 0 to 1024 S = set of set bits in m for each subset s of S t = bit set representing s SUM_{m}= max(SUM_{m}, SUM_{t}+ SUM_{m-t})

The complexity of the section right after mark 1 in the above pseudo-code is obviously **O(N**).

The complexity of the section right after mark 2 in the above pseudo-code is **O(3 ^{10})**. The proof of this complexity is left as an exercise to the reader

### CODE COMMENTARY

Till now, we have not talked about cardinality at all. This is because solving the problem to find the cardinality is just a small step above the solution described above.

We already know how to find the maximum sum.

We can maintain another array to store the cardinality of that maximum sum. Whenever we try to relax the sum with the same value, we must relax cardinality as well.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.