Leetcode Problem:
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;
}
};
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;
}
};
'알고리즘' 카테고리의 다른 글
| Total Characters in String After Transformations II (1) | 2025.05.15 |
|---|---|
| Total Characters in String After Transformations I (0) | 2025.05.14 |
| Minimum Equal Sum of Two Arrays After Replacing Zeros (1) | 2025.05.12 |
| Three Consecutive Odds (0) | 2025.05.11 |
| Count Number of Balanced Permutations (1) | 2025.05.10 |
짬뽕얼큰하게
