https://www.reddit.com/r/learnprogramming/comments/bwq48f/a_programming_competition_i_attempted_and_could/?st=jwi6ux94&sh=fde9fafe

largest_unique_digits_sum.py

from timeit import Timer

a = [984, 981, 976, 950, 899, 890, 887, 885, 880, 800, 798, 790, 777, 767, 750, 701, 697, 688, 680, 678, 650, 599, 589,
     567, 550, 501, 9, 8, 7, 6, 5, 4, 3, 2, 1]
b = [1090, 1080, 1074, 1065, 1057, 1056, 1047, 1041, 1041, 1038, 1025, 1013, 1008, 992, 991, 991, 991, 978, 977, 959,
     945, 935, 925, 925, 923, 915, 908, 904, 901, 901, 900, 897, 894, 882, 880, 876, 866, 854, 849, 849, 833, 818, 818,
     812, 811, 809, 798, 794, 793, 788, 772, 763, 747, 746, 743, 737, 736, 734, 732, 730, 728, 718, 714, 713, 706, 701,
     699, 691, 690, 689, 681, 672, 663, 656, 654, 653, 652, 651, 646, 644, 640, 637, 637, 635, 634, 633, 630, 625, 621]


# answer for b is [1041, 959, 882, 763] = 3645
# answer for a is 2425

def find_max_sum(arr):
    digits_to_largest_dict = {}  # maps a set of digits (as a tuple) to largest number in input
    num_to_digits_dict = {}  # maps a number to it's set of digits

    for n in arr:
        s = set([int(d) for d in str(n)])
        t = tuple(s)
        if t not in digits_to_largest_dict or (t in digits_to_largest_dict and n > digits_to_largest_dict[t]):
            digits_to_largest_dict[t] = n
            num_to_digits_dict[n] = s

    digit_sets = [set([]) for _ in range(10)]  # for each digit 0..9, the set of largest numbers containing this digit
    all_nums = set([])  # all of the largest numbers
    for digits, n in digits_to_largest_dict.items():
        for d in digits:
            digit_sets[d].add(n)
        all_nums.add(n)

    stack = [[]]
    max_sum = 0
    max_candidate = None
    while stack:
        candidate = stack.pop()

        sum_of_candidate = sum(candidate)
        if sum_of_candidate > max_sum:
            max_sum = sum_of_candidate
            max_candidate = candidate

        digits_in_candidate = set().union(*[num_to_digits_dict[n] for n in candidate])

        search_space = all_nums - set(candidate)
        for d in digits_in_candidate:
            search_space = search_space - digit_sets[d]

        for n in search_space:
            if not candidate or n > max(candidate):
                stack.append(candidate + [n])
    return max_sum, max_candidate


def main():
    t = Timer('find_max_sum(b)', setup="from __main__ import find_max_sum, b")
    number, time_taken = t.autorange()
    print(f'b: {time_taken/number} sec')
    # b: 0.026876546000000008 sec
    print(find_max_sum(b))
    # (3645, [763, 882, 959, 1041])

    t = Timer('find_max_sum(a)', setup="from __main__ import find_max_sum, a")
    number, time_taken = t.autorange()
    print(f'a: {time_taken/number} sec')
    # b: 0.0330791565 sec
    print(find_max_sum(a))
    # a: (2425, [1, 2, 3, 4, 688, 777, 950])


if __name__ == '__main__':
    main()