編程算法：字符串組合生成（位運算法）C++實現

編程算法：字符串組合生成（位運算法）C++實現

給定一個字符串，生成其所有非空子集組合（保持原序）。例如 "abc" 的組合為 a, b, c, ab, ac, bc, abc。本質上等價於對長度 n 的二進制數從 1 遍歷到 2^n - 1，每個比特位 1 表示選擇對應字符。本文給出基於位運算的簡潔 C++ 實現。

核心思路

• 字符串長度 n，共 2^n - 1 個非空子集。
• 整數 i (1 ≤ i < 2^n) 的二進制表示直接對應選擇方案：第 k 位為 1 選擇 s[k]。
• 利用位運算 i & 1 判斷最低位，i >>= 1 右移遍歷各位。

完整代碼

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

// 根據掩碼 i 生成對應子序列
string BinaryString(const string& s, int i) {
    string res;
    int k = 0;
    while (i) {
        if (i & 1) res.push_back(s[k]);
        ++k;
        i >>= 1;
    }
    return res;
}

// 生成所有非空組合
vector<string> Combination(const string& s) {
    vector<string> res;
    if (s.empty()) return res;
    int total = 1 << s.length();  // 2^n
    for (int i = 1; i < total; ++i) {  // 從 1 開始，排除空集
        res.push_back(BinaryString(s, i));
    }
    return res;
}

int main() {
    string s = "abc";
    vector<string> comb = Combination(s);
    for (const auto& str : comb) {
        cout << str << ' ';
    }
    cout << endl;
    return 0;
}

輸出結果

a b ab c ac bc abc 

複雜度分析

• 時間：O(n * 2^n)。外層循環 2^n 次，內層生成字符串最長 O(n)。
• 空間：O(n * 2^n) 存儲所有結果；若僅遍歷輸出不存儲，空間可降至 O(n)。

擴展與變體

1. 指定長度組合：在循環中增加 __builtin_popcount(i) == k 判斷。
2. 排列生成：需用遞歸回溯或 next_permutation，本質不同。
3. 大數據量優化：使用迭代器懶加載、位運算技巧（如 Gosper's Hack）跳過固定權重組合。

常見誤區

• 原文代碼中 for (int i=1; i 等片段顯然是編輯遺留的亂碼，正確循環條件為 i < total。
• pow(2.0, n) 返回 double，大 n 時精度丟失，應用移位 1 << n（n ≤ 30/62）。
• 結果順序與二進制計數順序一致（字典序非嚴格），若需字典序需額外排序。