Problem Statement in English

You are given an array of digits, where each digit is between 0 and 9. You need to find all the unique 3-digit even numbers that can be formed using the digits in the array. The numbers should not have leading zeros. Further, the generated numbers should be in ascending order.

Approach

You clearly need to generate every possible combination of 3 digits from the given digits. It’s just that you need to make sure that the number is even and does not have leading zeros.

So we shove all the digits into a hashmap, and then use a standard backtracking template.

One catch though, the combinations must be in ascending order. So we need to sort the keys of the hashmap first, and run the backtracking on those keys.

Also, remember to factor in that there are no leading zeros and that the last digit must be even.

Solution in Python


class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        count = Counter(digits)
        keys = sorted(count.keys())

        res = []
        temp = []

        def dfs(pos):
            if pos >= 3:
                if len(temp) == 3:
                    res.append(temp[0] * 100 + temp[1] * 10 + temp[2])
                return

            for k in keys:
                if not count[k]:
                    continue
                if pos == 2 and k % 2:
                    continue
                elif not pos and not k:
                    continue

                temp.append(k)
                count[k] -= 1

                dfs(pos + 1)

                temp.pop()
                count[k] += 1

        dfs(0)
        return res

Complexity

  • Time: $O(n!)$
    The time complexity is $O(n!)$ because we are generating all possible combinations of 3 digits from the given digits. The number of combinations is factorial in nature.

  • Space: $O(n)$
    The space complexity is $O(n)$ because we are using a hashmap to store the counts of each digit, and the maximum size of the hashmap is $n$.

And we are done.