Counting numbers that are divisible by 3 and can be produced from the digits of a given number I'm trying to solve this problem from codewars.


  Problem
  
  Given a certain number, how many multiples of three could you obtain with its digits? Suppose that you have the number 362. The numbers that can be generated from it are: 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632 and among those 3, 6, 36, 63 are  divisible by 3. 
  
  We need a function that can receive a number ann may output in the following order:
  
  
  the amount of multiples(without 0)
  the maximum multiple
  


My solution

I have found all possible permutations of the digits of the given number and checked if the number is divisible by 3. Here is my code - 

from itertools import permutations as perm
from functools import reduce

def to_int(digs):    # takes a list of digits of an integer and returns the number 
    n = reduce(lambda total, d: 10 * total + d, digs, 0)
    return n

def find_mult_3(num):
    digs = list(map(int, str(num)))
    perms = []        # stores all possible permutations with the digits of num
    for i in range(1, len(digs)+1):
        perms.extend(list(p) for p in set(perm(digs, i)))

    count, mx = 0, 0
    seen = set()      # to keep track of divisors already seen
    if 0 in perms:
        perms.remove(0)
    for p in perms:
        n = to_int(p)
        if n % 3 == 0 and n not in seen:
            if mx &lt; n:
                mx = n
            count += 1
            seen.add(n)

    return [count, mx]


But getting TLE, is there any way to make this program faster or any other clever way to solve this problem? Please ask if there is any need for clarification in any part of the code.
The algorithm can be improved, so that we do less work:

Use the fact that multiples of 3 have a sum of digits that's also a multiple of 3.  That means we can select all the distinct combinations of digits, and discard any that don't sum to a multiple of 3.  Only for those sets not discarded, we can compute the number of permutation of the selected digits.  (Note that we don't have to actually produce all the numbers, merely count them - so if we have n different digits, we count n! permutations; if p of them are identical, then n!/p!, and so on).

For example, with input 5532:


5+5+3+2 is 15, this gives us 4!/2! permutations that are multiples of 3 (and remember 5532 as the largest such multiple).
5+5+3 is 13, so ignore it.
5+5+2 is 12, giving us 3!/2! more permutations to add to our count.
5+3+2 is 10; ignore it.
5+5 is 10; ignore it.
5+3 is 8; ignore it.
5+2 is 7; ignore it.
2+3 is 5; ignore it.
5 alone - ignore
3 alone - add one to the count.
2 alone - ignore.


And we're done; the total count is 4!/2! + 3!/2! + 1 = 16.