The power of pruning in backtracking IV

Although this is marked as an easy problem, solving generically would make it a medium one. Standard backtracking but the key it to prune it: as soon as the number exceeds the min allowed, cut short the search space. Code is down below, cheers, ACC.

Unique 3-Digit Even Numbers - LeetCode

You are given an array of digits called digits. Your task is to determine the number of distinct three-digit even numbers that can be formed using these digits.

Note: Each copy of a digit can only be used once per number, and there may not be leading zeros.

 

Example 1:

Input: digits = [1,2,3,4]

Output: 12

Explanation: The 12 distinct 3-digit even numbers that can be formed are 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, and 432. Note that 222 cannot be formed because there is only 1 copy of the digit 2.

Example 2:

Input: digits = [0,2,2]

Output: 2

Explanation: The only 3-digit even numbers that can be formed are 202 and 220. Note that the digit 2 can be used twice because it appears twice in the array.

Example 3:

Input: digits = [6,6,6]

Output: 1

Explanation: Only 666 can be formed.

Example 4:

Input: digits = [1,3,5]

Output: 0

Explanation: No even 3-digit numbers can be formed.

 

Constraints:

• 3 <= digits.length <= 10
• 0 <= digits[i] <= 9

public int TotalNumbers(int[] digits)
{
    HashSet uniqueNumbers = new HashSet();
    int NDIGITS = 3;
    TotalNumbers(digits, "", (int)Math.Pow(10, NDIGITS - 1), (int)Math.Pow(10, NDIGITS), uniqueNumbers, new HashSet());
    return uniqueNumbers.Count;
}

public void TotalNumbers(int[] digits,
                        string number,
                        int min,
                        int max,
                        HashSet uniqueNumbers,
                        HashSet used)
{
    int n = 0;
    if (Int32.TryParse(number, out n))
    {
        if (n % 2 == 0 &&
            n >= min &&
            n < max &&
            !uniqueNumbers.Contains(n))
        {
            uniqueNumbers.Add(n);
        }
        if (n >= min) return;
    } 

    for (int i = 0; i < digits.Length; i++)
    {
        if (!used.Contains(i))
        {
            used.Add(i);
            TotalNumbers(digits, number + digits[i].ToString(), min, max, uniqueNumbers, used);
            used.Remove(i);
        }
    }
}