位運算技巧求集合所有子集（Java 實現）

位運算技巧求集合所有子集（Java 實現）

給定長度為 n 的集合，其子集總數為 2^n（含空集）。利用二進制位與元素一一對應，從 0 遍歷到 2^n - 1，即可輕鬆生成所有子集。本文提供通用實現，並延伸至 0-1 背包問題思路。

核心原理

• 集合 {a,b,c} 長度 3，子集數 8；
• 整數 0~7 的二進制：000, 001, 010, 011, 100, 101, 110, 111；
• 第 i 位為 1 表示選擇第 i 個元素；
• 補齊前導零對齊原數組下標。

完整代碼

public class SubsetsGenerator {
    private final String[] origin = {"a", "b", "c"};
    private String[] binaries;

    public static void main(String[] args) {
        new SubsetsGenerator().generate();
    }

    private void generate() {
        int total = 1 << origin.length; // 2^n
        binaries = new String[total];
        for (int i = 0; i < total; i++) {
            binaries[i] = Integer.toBinaryString(i);
        }
        padZeros();
        printSubsets();
    }

    private void padZeros() {
        for (int i = 0; i < binaries.length; i++) {
            String s = binaries[i];
            if (s.length() == origin.length) continue;
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < origin.length - s.length(); j++) sb.append('0');
            binaries[i] = sb.append(s).toString();
        }
    }

    private void printSubsets() {
        for (String bits : binaries) {
            StringBuilder subset = new StringBuilder();
            for (int i = 0; i < bits.length(); i++) {
                if (bits.charAt(i) == '1') subset.append(origin[i]);
            }
            System.out.println(subset.length() == 0 ? "∅" : subset);
        }
    }
}

輸出示例

∅
a
b
ab
c
ac
bc
abc

延伸應用：0-1 背包問題

同樣遍歷所有子集（即所有物品組合），過濾總重量 ≤ 容量的組合，計算價值總和取最大值。雖然指數級複雜度僅適合小規模（n ≤ 20），但思路清晰，是動態規劃之前的直觀理解。