Maximum Sum of Array With No Repeating Digits

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 bitsets 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 bitsets 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 Ai
    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.

C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

int maxSum(vector<int> &A) 
{
    int sum[1024] = {0};
    int num;

    int n = A.size();

    for(int i = 0; i < n; i++)
    {
        num = A[i];
        int nm = 0;
        while(num)
        {
            nm |= (1 << (num % 10));
            num /= 10;
        }
        sum[nm] = max(sum[nm], A[i]);
    }

    for(int i = 0; i < n; i++)
    {
        num = A[i];
        int nm = 0;
        while(num)
        {
            nm |= (1 << (num % 10));
            num /= 10;
        }

        for(int j = 0; j < 1024; j++)
        {
            if((nm & j) == 0)
                sum[nm + j] = max(sum[nm + j], sum[nm] + sum[j]);
        }
    }

    int mx = 0;

    for(int i = 0; i < 1024; i++)
        mx = max(mx, sum[i]);
    return mx;
}