經典算法：字符串所有組合的遞歸生成

問題描述

給定一個字符串，輸出其所有非空子集（組合），即從中選取 1 到 n 個字符的所有可能排列。例如 "abc" 輸出 a, b, c, ab, ac, bc, abc。

遞歸思想

對於字符串的第一個字符，有兩種選擇：

1. 選中它：加入當前組合，遞歸處理剩餘 n-1 個字符，需再選 m-1 個。
2. 不選它：不加入組合，遞歸處理剩餘 n-1 個字符，仍需選 m 個。

終止條件：m == 0（輸出當前組合）或字符串為空（返回）。

C++ 實現

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

void combination(const char* str, int m, vector<char>& path) {
    if (m == 0) {
        for (char c : path) cout << c;
        cout << '\n';
        return;
    }
    if (*str == '\0') return;
    // 選擇當前字符
    path.push_back(*str);
    combination(str + 1, m - 1, path);
    path.pop_back();
    // 不選擇當前字符
    combination(str + 1, m, path);
}

void all_combinations(const char* str) {
    if (!str) return;
    int len = strlen(str);
    vector<char> path;
    for (int m = 1; m <= len; ++m) {
        combination(str, m, path);
    }
}

int main() {
    char s[] = "abc";
    all_combinations(s);
    return 0;
}

複雜度與變體

• 時間 O(2^n)，空間 O(n)（遞歸棧 + 路徑存儲）。
• 若需輸出全排列而非組合，可在選中字符後對剩餘字符全排列，或使用 next_permutation。
• 去重：若字符串含重複字符，先排序並在遞歸中跳過相同字符（if (i > start && str[i] == str[i-1]) continue;）。