백준 6443번 애너그램 C++

https://www.acmicpc.net/problem/6443

6443번: 애너그램

 

전체 문자열에 대해 백트래킹을 시도하면 시간초과가 나서 알파벳 개수에 대해 백트래킹으로 하니까 중복, 정렬 문제도 자연스럽게 해결이 되도록 풀렸다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, len;
string str;
vector<int> visited;
string ans;

void BT() {
    if (ans.length() == len) {
        cout << ans << "\n";
        return;
    }
    for (int i = 0; i < 26; i++) {
        if (visited[i] == 0) continue;
        visited[i]--;
        ans += 'a' + i;
        BT();
        visited[i]++;
        ans.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    while (n--) {
        cin >> str;
        len = str.length();
        visited = vector<int>(26, 0);
        ans = "";
        for (int i = 0; i < len; i++) {
            visited[str[i] - 'a']++;
        }
        BT();
    }
}