字符串組合生成：遞歸回溯與位運算兩種算法詳解

問題

輸入字符串，輸出所有非空字符組合。例："abc" → a、b、c、ab、ac、bc、abc。

方法一：遞歸回溯

• 對長度 n 的字符串，枚舉選擇 m=1..n 個字符。
• 遞歸函數 Combination(str, m, result)：當前字符可選或不選，選則 m-1，不選則 m 不變，指針後移。
• 終止條件：m==0 輸出結果；str==NULL 或 *str=='\0' && m>0 返回。

void Combination(char *str, unsigned int m, vector<char> &result) {
    if (!str || (*str=='\0' && m>0)) return;
    if (m==0) { Print(result); return; }
    result.push_back(*str);
    Combination(str+1, m-1, result);
    result.pop_back();
    Combination(str+1, m, result);
}

方法二：位運算枚舉

• 用 n 位二進制數表示選擇，1 選 0 不選。
• 從 1 循環到 (1<，逐位檢查輸出對應字符。
• 時間 O(n·2^n)，限制 n ≤ 32。

void StringCombinationUsingBitwise(char *str) {
    int len = strlen(str);
    if (len >= 32) return;
    int sum = 1 << len;
    for (int i = 1; i < sum; ++i) {
        for (int j = 0; j < len; ++j)
            if ((i>>j)&1) printf("%c", str[j]);
        printf("\n");
    }
}