Introduction

What happens when a small collection of digits needs to be arranged into valid three-digit numbers?

There are several conditions to satisfy at the same time:

1. The number must contain exactly three digits.
2. The first digit cannot be 0.
3. The number must be even.
4. A digit can only be used as many times as it appears in the input.
5. Duplicate numbers should be counted only once.

Because the input contains at most 10 digits, backtracking is a natural approach. Every possible arrangement can be generated, checked, and stored in a HashSet to ensure that only distinct numbers are counted.

Question Link

LeetCode 3483 – Unique 3-Digit Even Numbers

Approach

The idea is to build the number one digit at a time.

A recursive function maintains:

1. curr — the number currently being constructed.
2. boo[] — tracks which positions of the input array have already been used.
3. ms — a HashSet containing all valid three-digit numbers.

At every recursion level, each unused digit is selected and appended to curr.

Once three digits have been selected, three checks are performed:

Leading zero

is not a valid three-digit number, so it is rejected.

Even number

The generated number must be divisible by 2.

Distinctness

The generated number is inserted into a HashSet, which automatically removes duplicates.

Why Track Indices Instead of Digits?

Consider:

The digit 2 appears twice.

Therefore, a valid number such as:

must be allowed.

The boolean array tracks positions, not just digit values:

The two copies of 2 are therefore treated as two separate usable elements.

The HashSet handles the other side of the problem: different index selections can produce the same number, but the final answer should count that number only once.

Java Implementation

Backtracking in Action

Consider:

The recursion starts with an empty string:

Choose 1:

Then choose 2:

Then choose 3:

The number has three digits, but 123 is odd, so it is rejected.

Backtracking returns to:

and tries 4:

This number is three digits, does not start with zero, and is even.

Therefore:

The recursion continues exploring other arrangements.

Handling Duplicate Digits

Consider:

The two 2s have different indices.

Some recursion branches may therefore generate the same number:

from different copies of 2.

Without a HashSet, these would be counted multiple times.

With:

only one copy remains.

The valid numbers are:

Therefore:

Dry Run

Consider:

Some of the generated permutations include:

The recursion continues for all possible selections.

Eventually, the set contains:

So:

The final answer is:

Why a HashSet Is Useful

There are two separate concerns in this problem.

Generating valid arrangements

Backtracking ensures that every possible selection of three positions is explored.

Removing duplicates

The HashSet ensures that identical numbers generated through different index choices are counted only once.

This combination is especially useful when the input contains duplicate values.

Complexity Analysis

Let n be the number of digits.

At most 10 digits are given, and only three positions are selected.

The number of possible index arrangements is:

Therefore, the number of generated arrangements is O(n³).

For each completed arrangement, converting/checking the three-digit number takes constant time because the number always has exactly three digits.

Time Complexity

O(n³)

With n ≤ 10, this is very small in practice.

Space Complexity

The recursion depth is at most 3, while the HashSet stores the distinct valid numbers.

So the auxiliary recursion space is O(1), excluding the result set.

The result set contains at most a constant number of three-digit numbers because there are only 900 possible three-digit numbers.

A Simpler Observation

There is another way to think about the problem.

A three-digit even number has the structure:

The units digit must be one of:

The hundreds digit cannot be zero.

The tens digit can be any remaining available digit.

This means the problem could also be solved by directly choosing:

and checking whether the resulting number is valid.

The backtracking solution generalizes this idea nicely because it systematically explores all possibilities.

Interview Tip

When a problem asks to create numbers, strings, or arrangements from a small collection of elements, look for permutation/backtracking patterns.

A useful checklist is:

For this problem:

That immediately points toward a small backtracking solution.

Conclusion

LeetCode 3483 is a good introduction to combining backtracking with duplicate handling.

The recursive function explores every possible three-digit arrangement while the boolean array ensures that each input position is used at most once. Once a number is completed, it is checked for the leading-zero and even-number conditions.

Finally, a HashSet guarantees that duplicate numbers are counted only once.

With at most 10 input digits and only three positions to fill, the brute-force search remains highly efficient and easy to understand.