416. Partition Equal Subset Sum：用「開關箱」和「位元魔法」秒殺動態規劃！

Sep 6, 2026

想像一下：這題到底在玩什麼？

你有沒有玩過那種解謎遊戲？地上擺著一堆裝了不同重量積木的箱子，系統要求你把它們分成「重量一模一樣的兩堆」。如果分得出來就過關，分不出來就 Game Over。

這就是 LeetCode 416（Partition Equal Subset Sum，分割等和子集合）。

很多人一看到這題，腦袋立刻浮現超複雜的數學公式。但放輕鬆，今天我們不背公式，我們用「家裡的電燈開關」和「電腦晶片的超能力」，一口氣把動態規劃（DP）徹底搞懂！

概念暖身：大人的黑話「半環」，其實就是你的日常直覺

在進入題目之前，我們先聊聊很多工程師喜歡拿來裝酷的名詞：「半環（Semiring）」。

不要被這個像魔法咒語的名字嚇到了！你可以把它想像成一個「遊戲規則包」。

平時我們在學校學的加減乘除，是一套規則包（數字相加、數字相乘）。但在寫程式時，聰明的工程師發現：如果我們換一套運算規則，很多看起來完全不同的問題，居然全都是同一種題目！

這就是所謂的「通靈」——不是瞎猜，而是看穿了背後的本質模式。

規則包一：地圖導航（走最短路）

你在算從家裡到學校怎麼走最快。
加法換成「選最小」：走兩條路，你只想要花費時間比較短的那條（min）。
乘法換成「累加路程」：前半段花了 5 分鐘，後半段花了 10 分鐘，加起來花了 15 分鐘（+）。

規則包二：我們的開關箱（布林半環）

回到我們這道題目。請注意，題目根本不在乎你最後抓了哪幾顆積木，也不在乎總共有幾萬種擺法。

題目只在乎一句話：「到底做不做得到？」

答案只有兩種：行（1 / 綠燈） 或 不行（0 / 紅燈）。

在這種只有開和關的世界裡，我們的規則包變成了「布林半環」：

「或」運算（OR，代表收集所有可能性）：

只要任何一條路走得通，燈就會亮！
亮 + 滅 = 亮（只要有一種選法能湊出這個重量，就算成功）。
它的安靜守護者（單位元素）是「滅 / false」：任何狀態跟 false 做 OR，都完全不影響原本的狀態（True OR False = True；False OR False = False）。所以我們一開始把所有的可能都預設成 false，代表「還沒探索到」。

「與」運算（AND，代表限制與串聯）：

必須前一步走得通，而且這一步也走得通，最後才會通！
亮 × 亮 = 亮。
它的安靜守護者（單位元素）是「亮 / true」：任何狀態跟 true 做 AND，依然保持原樣。

所以，動態規劃的核心精神其實超簡單： 「我現在這個重量能不能湊得出來？＝我原本就湊得出來（OR）我從前面的某個重量再加上現在這顆積木（AND）。」

看懂了這套規則包，你就不再只是死背題目，因為不管是找最短路徑、算機率、還是玩開關燈，本質上都是同一台 DP 機器在不同規則包下的運作而已！

動手寫解法：一步步拆解

第一關：先抓出不可能的倒楣鬼

既然題目說要分成兩堆一模一樣重的積木，那所有積木的「總重量」一定得是偶數吧？

如果是奇數（例如總共 15 公斤），你怎麼切都不可能切成兩個整數重量。遇到這種情況，連算都不用算，直接跟系統說「不行」！

int total = std::accumulate(nums.begin(), nums.end(), 0);

// 如果總和是奇數，直接回家睡覺，不可能平分！
if (total % 2 != 0) return false;

// 我們的目標：只要能湊出總重量的一半就算贏！
int target = total / 2;

第二關：擺出一排開關箱

假設目標是一半的重量 target，我們就準備一長排電燈開關。第 0 格代表重量 0，第 1 格代表重量 1……第 target 格代表我們要的目標。

一開始，所有開關都是關閉的（0 / false）。只有一個開關是預設打開的：第 0 格！為什麼？因為「一個積木都不拿」，總重量就是 0，這絕對是百分之百做得到的！

// 題目說每個數字最大 100，陣列最多 200 個，所以總和最多 20000，一半最多 10000
// std::bitset 就是一台超級省空間、專門放開關燈的機器
std::bitset<10001> dp;

// 什麼都不拿，就能湊出 0，第 0 盞燈點亮！
dp[0] = true;

第三關：輪流丟入積木，見證魔法時刻！

現在，我們把口袋裡的積木一個一個拿出來看。

假設我們抽到了一塊重量為 num 的積木。對於任何一個重量，我們都有兩個選擇：

不放這塊積木：原本能亮的燈繼續亮著（維持 dp 原樣）。
放這塊積木：如果之前重量 k 的燈是亮的，那現在重量 k + num 的燈也能被點亮！

如果照傳統寫法，你得寫個迴圈，由大到小一個一個去檢查跟改燈。

但別忘了，我們在電腦的世界裡！電腦的 CPU 最擅長做一件事：一口氣把整排開關往左推！

如果我把整個 dp 開關箱往左位移 num 格（寫成 dp << num），就相當於「把所有目前能湊出來的重量，一口氣通通加上 num」！

然後，我們用「OR（|）」把原本的狀態跟新產生的狀態疊加在一起：

for (int num : nums) {
    // 這一行就是魔法的全部！
    // dp：原本就能湊出的重量（不選當前積木）
    // (dp << num)：把以前能湊出的所有重量，全部加上 num（選了當前積木）
    // |= ：只要有一種方法行得通，燈就點亮！
    dp |= (dp << num);
}

// 最後只要看 target 那盞燈有沒有亮著，就知道答不答得出來！
return dp[target];

慢動作重播：假設我們拿到一塊重量為 3 的積木

原本的燈箱狀態：dp = ...00001（只有重量 0 是亮的）
往左推 3 格：dp << 3 = ...01000（重量 3 被點亮了）
它們相加（OR）：新的 dp = ...01001（現在重量 0 和 3 都是亮的了！）

整排開關在一個瞬間全部完成更新，完全不需要你寫迴圈在那邊一個一個慢慢搬。

完整程式碼：短到不可思議

把上面的步驟全部拼在一起，就變成了這份極度優雅、速度快到飛起的解答：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = std::accumulate(nums.begin(), nums.end(), 0);
        
        // 奇數不可能平分
        if (total % 2 != 0) return false;
        
        int target = total / 2;
        
        // 準備我們的燈箱，第 0 格亮起
        std::bitset<10001> dp;
        dp[0] = true;
        
        // 每摸到一個數字，整排開關一口氣向左平移並疊加
        for (int num : nums) {
            dp |= (dp << num);
        }
        
        // 目標燈有沒有亮？
        return dp[target];
    }
};

總結：我們學到了什麼？

換個規則看世界（半環思考）：動態規劃不是一堆無聊的符號。當你發現問題只在乎「行不行」時，傳統的加乘就變成了「OR 與 AND」。這套思考框架能讓你把背包問題、圖論路徑問題串在同一個腦袋模型裡。
不要做無用功：先做奇偶數檢查，奇數直接踩煞車，省下一整大段白費的計算時間。
榨乾 CPU 的硬體超能力：傳統背包 DP 跑迴圈要一個格子一個格子填；但利用 C++ 的 std::bitset 加上位移運算 dp << num，CPU 可以一次打包 64 個開關甚至更多一起算。這不僅程式碼短到只有十來行，執行速度更直接提升了數十倍！