1342번

1342번 - 행운의 문자열

각 문자열의 갯수를 세고, 앞의 문자랑만 다르게 하면서 재귀함수를 이용해서 구현하면 된다.

백트래킹 문제

<정답 코드>

#include<iostream>
#include<string>
using namespace std;
int cnt[26];
int ans = 0;
 
void go(int n,int p)
{
    if (n == 0)
    {
        ans += 1;
        return;
    }
 
    for (int i = 0; i < 26; i++)
    {
        if (cnt[i] > 0 && i!=p)
        {
            cnt[i] -= 1;
            go(n - 1, i);
            cnt[i] += 1;
        }
    }
 
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    string s;
    cin >> s;
 
    for (int i = 0; i < s.size(); i++)
    {
        cnt[s[i] - 'a']++;
    }
 
    go(s.size(),-1);
 
    cout << ans << "\n";
 
    return 0;
}