10776 Determine The combination

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

在 排列組合的課程中老師給了一個作業，要從字串 s 中產生所有的長度為 r 的組合。所謂長度為 r 的組合指的是從字串 s 中挑選 r 個字元。對於相同的組合，但是排列不同的，只考慮 r 個字元為 「非遞減（non-decreasing）」順序的那個。例如：ab 與 ba 為相同的組合，我們只要產生 ab 就好。

所給的字串中只會有小寫的字元，但是相同的字元可能會出現超過一次。請參考Sample Inout, Sample Output。

輸入

輸 入含有多筆測資。每筆測資一列，含有一個字串 s（長度介於 1 到 30 之間）和一個整數 r（0 < r <= s的長度）。

輸出

請 每筆測資輸出所有從 s 中產生長度為 r 的不同的組合。每個組合一列，按字典數序輸出。你可以確定最多只會有1000個不同的組合。

Sample Input

abcde 2
abcd 3
aba 2

Sample Output

ab
ac
ad
ae
bc
bd
be
cd
ce
de

abc
abd
acd
bcd

aa
ab

解題想法

• 字母輸入的順序可以隨意，所以我們要將收到的按照順序分類並且記錄每種字母的個數
• 所以babcaa會被轉成 a = 3, b = 2, c = 1 的形式記錄下來
• 因為ab跟ba是重複的，會取用ab，所以我們在求答案時都會先用a再來是b,c,d,e......
• 放完a後下一個也接著放a，變成aa，如果沒有a可以放才接著放b或c之類的字母
• 當a還有剩，但是字串的長度已經到我們輸入的n時，假如說n=2，那麼aa就是其中一個答案，把它cout出來

解答

#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];
int charTypeCount;

void dfs(int, int, int);

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]++;
            }
        }

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

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

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

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