Существуют ли какие-либо реальные алгоритмы O (n ^ n)?

Есть ли какой-нибудь реальный алгоритм с временная сложность O (n ^ n), это не просто уловка?

Я могу создать такой алгоритм, например, вычислить n ^ n за O (n ^ n) / Θ (n ^ n):

long n_to_the_power_of_m(int n, int m) {
    if(m == 0) return 1;
    long sum = 0;
    for(int i = 0; i < n; ++i)
        sum += n_to_the_power_of_m(n, m-1);
    return sum;
}

(требуется более 4 минут для вычисления 10 ^ 10)

Или наоборот: есть ли проблемы, которые нельзя решить лучше, чем за O (n ^ n)?