Finding 3-Digit Even Numbers

Leetcode Problem:

• Finding 3-Digit Even Numbers

Summary

• Find all unique even integers that can be formed by concatenating three digits from the given array in any order, without leading zeros.

Approach

• This solution uses a backtracking approach with recursion to generate all possible combinations of three digits from the input array
• It checks if each generated number is even and inserts it into a set if it is
• Finally, it returns a sorted vector of unique even numbers.

Complexity

• O(2^n * n), where n is the number of digits in the input array
• This is because in the worst case, the function generates all possible combinations of three digits, and for each combination, it checks if the generated number is even.

Explanation

• The solution starts by sorting the input array to ensure that the digits are in ascending order
• It then defines a recursive function combi to generate all possible combinations of three digits
• For each combination, it checks if the generated number is even and inserts it into a set if it is
• Finally, it returns a sorted vector of unique even numbers.

Solution Code:

class Solution {
public:
    set s;
    vector ans;
    bool visited[100] = {false,};
    void combi(vector& digits, int depth, int num){
        if(depth == 3){
            if(num % 2 == 0){
                s.insert(num);
            }
            return;
        }
        for(int i = 0 ; i < digits.size(); i++){
            if(visited[i]) continue;
            int n = num * 10 + digits[i];
            if(n == 0) continue;
            visited[i] = true;
            combi(digits, depth+1, n);
            visited[i] = false;
        }
    }
    vector findEvenNumbers(vector& digits) {
        sort(digits.begin(), digits.end());
        combi(digits, 0, 0);
        for (int num : s){
            ans.push_back(num);
        }
        return ans;
    }
};