[C++] [CSES] Creating Strings (Introductory Problems)

CSES의 열 다섯번째 문제입니다.

중복순열을 출력하는 문제입니다. 이것은 백준의 N과 M 시리즈를 풀어보셨다면 백트래킹으로 구현이 가능합니다.

 

Task

 

Given a string, your task is to generate all different strings that can be created using its characters.

Input

The only input line has a string of length n. Each character is between a–z.

Output

First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.

Constraints

• 1≤n≤8

Example

Input:
aabac

Output:
20
aaabc
aaacb
aabac
...
caaba
cabaa
cbaaa

 

Code

#include<bits/stdc++.h>
using namespace std;
string s;
set<string> st;
int vis[10];
void create(int idx, string cur){
    if (idx == s.size()){
        st.insert(cur);
        return;
    }
    for (int i=0;i<s.size();i++){
        if (!vis[i]){
            vis[i] = 1;
            create(idx + 1, cur + s[i]);
            vis[i] = 0;
        }
    }
}
int main(){
    cin >> s;
    sort(s.begin(), s.end());
    create(0, "");
    cout << st.size() << "\n";
    for (string ss : st) cout << ss <<"\n";
}

생각해야 하는 것

• vis 배열을 통해 방문했던 곳을 패스하는 것이 중요합니다.
• 중복된 문자열을 제거해야하고, 알파벳순으로 출력해야 하므로 set<string>을 사용했습니다. set은 순서가 유지되고, 중복된 것을 허용하지 않습니다.