Problem Statement in English

You are given a list of integers.

Your task is to return the number of all possible unique 3 digit even numbers that can be formed using the digits in the list.

$0$ cannot be the first digit of a number.

Approach

This is a classic backtracking problem.

We will use a depth-first search (DFS) approach to explore all possible combinations of digits to form 3-digit even numbers.

Just make it easier for yourself by dumping everything into a Counter.

Solution in Python


class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        c = Counter(digits)

        def dfs(i):
            res = 0

            if i > 3:
                return 1

            for k, v in c.items():
                if (not k and i == 1) or not v or (i == 3 and k%2):
                    continue

                c[k]-=1
                res += dfs(i+1)
                c[k]+=1

            return res

        return dfs(1)

Complexity

  • Time: $O(3^n)$
    Since we try $n$ numbers for each spot in the 3-digit number, the time complexity is $O(3^n)$.

  • Space: $O(n)$
    Since we only store the digits in a Counter, the space complexity is $O(n)$.

And we are done.