字符串組合生成算法：基於位運算的全排列實現

問題描述

給定一個字符串（如 "abc"），輸出其所有非空子集組合，保持原字符相對順序。即：a, b, c, ab, ac, bc, abc。

本質上等價於生成長度為 n 的二進制數的所有非零組合（001, 010, 011, 100, 101, 110, 111），每個 bit 位對應是否選取該字符。

算法思路

1. 字符串長度為 n，總組合數為 2^n - 1（排除全 0）。
2. 遍歷 1 到 2^n - 1，將每個整數視為位掩碼。
3. 對掩碼的每一位，若為 1 則選取對應位置的字符拼接結果。

C++ 代碼實現

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

// 根據掩碼 i 從字符串 s 提取字符
string BinaryString(string s, int i) {
    string tmp;
    int k = 0;
    while (i != 0) {
        if (i & 0x1) tmp.push_back(s[k]);
        k++;
        i >>= 1;
    }
    return tmp;
}

// 生成所有組合
vector<string> Combination(string s) {
    vector<string> vs;
    if (s.length() == 0) return vs;
    int num = pow(2.0, s.length());
    for (int i = 1; i < num; i++) { // 從 1 開始，排除空集
        vs.push_back(BinaryString(s, i));
    }
    return vs;
}

int main() {
    string s = "abc";
    vector<string> vs = Combination(s);
    for (size_t i = 0; i < vs.size(); i++)
        cout << vs[i] << " ";
    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)。
• 對於超長字符串（n > 31/63），需使用大整數或遞歸/迭代生成組合，避免位掩碼溢出。
• 若需字典序輸出，可對結果排序或調整生成順序（如遞歸按選/不選決策）。

總結

利用位運算生成組合是經典、高效的技巧，代碼簡潔且無遞歸開銷。理解「位掩碼與子集的一一對應」是解決此類組合生成問題的核心鑰匙。