10776 Determine The combination

題目：http://luckycat.kshs.kh.edu.tw/homework/q10776.htm 觀念：DFS 難度：luckycat ★★

#include <bits/stdc++.h>
#include <algorithm>
#include <string.h>
using namespace std;

//ch紀錄字母，ch_num紀錄字母出現的次數
char ch[50];
int ch_num[50];
char ans[50];

//n為還剩下幾個字母要合併，m為字母種類數量
//i
void dfs(int n, int m, int i, int index) {

    if(n == 0) {
        //找出其中一個解答，則輸出該解答
        puts(ans);//輸出char陣列，也可用for迴圈輸出
        return;
    }
    for(; i < m; i++) {

        if(ch_num[i]) {
            ch_num[i]--; //假如說a有3個，因為其中一個a被放進答案裡面，所以a變2個
            ans[index] = ch[i]; //答案的最後一格放入目前的字母
            dfs(n-1, m, i, index+1);
            ch_num[i]++; //因為dfs在往回走，a這字母又從答案中被退出來，所以從2個變回3個，
        }
    }
}

int main() {

    // 輸入 abdbcaa 4
    // sort 後 abdbcaa 會變成 aaabbcd
    // ch     => {'a','b','c','d'}
    // ch_num => { 3 , 2 , 1 , 1 }

    char str[30]; //要輸入的字串，如：abcde
    int n, len, i, j;

    while(cin>>str>>n) { //舉例：abcde 2

        len = strlen(str); //sizeof(str)也可以

        sort(str, str+len); // abdbcaa會變成aaabbcd

        //將重複的字母計數處理
        ch[0] = str[0], ch_num[0] = 1;
        for(i = 1, j = 0; i < len; i++) {
            if(str[i] != str[i-1]) {
                j++;
                ch[j] = str[i];
                ch_num[j] = 1;
            } else {
                ch_num[j]++;
            }
        }

        int charTypeCount = j+1; //charTypeCount為字母種類數量，範例為4

        dfs(n, charTypeCount, 0, 0);
    }
    return 0;
}