C# 求冪集：List<BitArray> 深拷貝與值引用問題完美解決

問題回顧

遞歸生成冪集時，將中間列表 B 加入結果集 C：C.Add(B)。因為 List<T> 是引用類型，直接添加會導致結果集中所有元素指向同一個列表對象，最終全變成最後狀態 (空列表)。需在添加時創建副本 (深拷貝)。

錯誤代碼片段

if (i == A.Count) {
    C.Add(B); // ❌ 直接添加引用，後續 B 修改會影響已加入的元素
    // ...
}

正確解法：三種深拷貝方式

1. 构造函數拷貝 (最簡潔、推薦)

C.Add(new List<BitArray>(B)); // 或 C.Add(B.ToList());

List<T> 的構造函數接受 IEnumerable<T>，會創建新列表並複製所有元素引用。因為 BitArray 是類 (引用類型)，這裡是**淺拷貝列表結構，元素仍共享同一 BitArray 對象**。但冪集算法中 B 的元素來源於原始輸入 A，且不會修改元素內部狀態，僅增刪列表項，所以**淺拷貝列表即可滿足需求**。

2. 手動 new List + AddRange

var copy = new List<BitArray>();
copy.AddRange(B);
C.Add(copy);

3. LINQ ToList() (語義最清晰)

C.Add(B.ToList()); // 內部同構造函數拷貝

完整修正後核心遞歸代碼

void GetPowerSet(int i, List<BitArray> A, List<BitArray> B, ref List<List<BitArray>> C) {
    if (i == A.Count) {
        C.Add(B.ToList()); // ✅ 關鍵修正：創建副本
        return;
    }
    BitArray x = A[i];
    B.Add(x);
    GetPowerSet(i + 1, A, B, ref C);
    B.RemoveAt(B.Count - 1); // 回溯
    GetPowerSet(i + 1, A, B, ref C);
}

驗證結果

輸入 A = {1,2,3} (用 BitArray 表示)，輸出 C.Count == 8，且每個子集獨立：

{} 
{1} 
{2} 
{1,2} 
{3} 
{1,3} 
{2,3} 
{1,2,3}

補充：BitArray 深拷貝 (若需修改元素內部位)

若後續需修改副本中的 BitArray 位值，需深拷貝元素：

C.Add(B.Select(ba => new BitArray(ba)).ToList()); // 每個 BitArray 都新建副本

總結

• List<T> 無 Clone() 方法，用 構造函數 `new List<T>(source)` 或 `source.ToList()` 實現列表級淺拷貝。
• 冪集遞歸中，**列表級淺拷貝已足夠**，因為元素 (BitArray) 不被修改，只被引用。
• 若元素可變且需隔離，請在拷貝時對元素逐個 new BitArray(old)。