一、學習目標

• 了解以 bitmask 表示子集合與其時間/空間複雜度
• 掌握 dp[mask]（或 dp[mask][i]）的狀態設計與轉移。
• 熟悉 子集合枚舉、超集合枚舉、子集合和（SOS DP）等技巧。
• 能將分配/分組/路徑類問題轉為子集合 DP 實作（如任務分配、乘電梯、分桶）。

二、觀念說明

• Bitmask 表示：用第 j 位（0/1）表示第 j 個元素是否被選。
• 典型狀態：
  • 分配型：dp[mask] = 已分配 mask 時的最佳代價（常配合 i = popcount(mask) 表示已分配的人數/物件數）。
  • 分桶型：dp[mask] = 已選元素的當前桶內和（mod 目標）。
  • 路徑型：dp[mask][i] = 造訪 mask，且以 i 結尾的最佳值。
• 子集合枚舉（從某個集合 m 枚舉其所有子集合 s）：

for (int s = m; ; s = (s - 1) & m) {
    // 使用子集合 s
    if (s == 0) break;
}

• 超集合枚舉（從 m 枚舉所有超集合 s，常見於 SOS DP）：

for (int s = m; s < (1<<n); s = (s + 1) | m) {
    // s 是 m 的超集合
}

• 常見優化：
  • 依問題特性排序（如降序）以便剪枝。
  • 以 pair（或自定 struct）存兩個比較關鍵指標並做字典序最小化。
  • 記憶化 unordered_map<int,int> 或 vector 當作訪問狀態表。

三、CSES實戰演練

題目1:Task Assignment

原題:
https://cses.fi/problemset/task/2129

題意：
有 n 個人與 n 項任務，給定代價矩陣 cost[i][j]，每人分到 exactly 一個任務，最小化總成本。

解題思路：

• 狀態：dp[mask] = 已把 mask 中的任務分配給前 i = popcount(mask) 個人時的 最小成本。
• 轉移：對尚未取用的任務 j，更新 dp[mask | (1<<j)]。

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<vector<long long>> cost(n, vector<long long>(n));
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>cost[i][j];

    const long long INF = (long long)4e18;
    int M = 1<<n;
    vector<long long> dp(M, INF);
    dp[0] = 0;

    for(int mask=0; mask<M; ++mask){
        int i = __builtin_popcount((unsigned)mask); // 已分配的人數
        if(i>=n) continue;
        if(dp[mask] == INF) continue;
        for(int j=0;j<n;j++){
            if(!(mask & (1<<j))){
                int nxt = mask | (1<<j);
                dp[nxt] = min(dp[nxt], dp[mask] + cost[i][j]);
            }
        }
    }
    cout << dp[M-1] << "\n";
    return 0;
}

題目2:Elevator Rides

原題:
https://cses.fi/problemset/task/1653

題意：
每個人重量 w[i]，電梯容量 x，希望載完所有人所需最少趟數。

解題思路：

• 狀態：dp[mask] = pair<rides, last_weight>[
  • rides：到目前為止的趟數
  • last_weight：當前這一趟已載重量（越小越好）
• 轉移：嘗試把一位未上電梯的人加入目前趟，若超重就開新趟。
• 比較：字典序最小（先比較 rides，再比較 last_weight）。](http://)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long x; 
    if(!(cin>>n>>x)) return 0;
    vector<long long> w(n);
    for(int i=0;i<n;i++) cin>>w[i];

    int M = 1<<n;
    const long long INF = (long long)4e18;
    vector<pair<int,long long>> dp(M, {n+1, INF});
    dp[0] = {1, 0}; // 空集合視為開第一趟、重量 0（常見做法）

    auto better = [](pair<int,long long> a, pair<int,long long> b){
        if(a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    };

    for(int mask=0; mask<M; ++mask){
        auto [r, cur] = dp[mask];
        if(r==n+1) continue;
        for(int i=0;i<n;i++){
            if(!(mask & (1<<i))){
                pair<int,long long> cand;
                if(cur + w[i] <= x) cand = {r, cur + w[i]};
                else cand = {r+1, w[i]};
                int nxt = mask | (1<<i);
                if(better(cand, dp[nxt])) dp[nxt] = cand;
            }
        }
    }
    cout << dp[M-1].first << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Partition to K Equal Sum Subsets

原題:
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

題意：把陣列分成 k 個子集合，使每組和相等。

解題思路：

• 檢查 sum % k == 0，目標 target = sum/k，若有元素 > target 直接 false。
• 狀態：dp[mask] = 已放入的元素在當前桶中的和 (mod target)（-1 表示不可達）。
• 初態：dp[0]=0。
• 轉移：從可達的 mask 嘗試加入一個未選 i，若 dp[mask] + nums[i] <= target，
• dp[mask|1<<i] = (dp[mask] + nums[i]) % target。
• 結果：dp[(1<<n)-1] == 0 代表恰好分為 k 組。

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        long long sum = accumulate(nums.begin(), nums.end(), 0LL);
        if(sum % k) return false;
        int n = nums.size();
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if(nums[0] > target) return false;

        int M = 1<<n;
        vector<int> dp(M, -1);
        dp[0] = 0;
        for(int mask=0; mask<M; ++mask){
            if(dp[mask] == -1) continue;
            for(int i=0;i<n;i++){
                if(!(mask & (1<<i))){
                    if(dp[mask] + nums[i] <= target){
                        int nxt = mask | (1<<i);
                        int val = (dp[mask] + nums[i]) % target;
                        if(dp[nxt] == -1) dp[nxt] = val;
                        // 可加速：若裝滿一桶（val==0）通常更有利，亦可不覆蓋舊值
                    }
                }
            }
        }
        return dp[M-1] == 0;
    }
};

題目2:Matchsticks to Square

原題:
https://leetcode.com/problems/matchsticks-to-square/

題意：用一堆火柴是否能組成正方形（四邊等長）。

解題思路：

• sum % 4 == 0，target = sum/4。
• 狀態轉移同上：dp[mask] = 當前邊的長度 (mod target)。
• 結果：dp[(1<<n)-1] == 0。

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        long long sum = accumulate(matchsticks.begin(), matchsticks.end(), 0LL);
        if(sum % 4) return false;
        int target = sum / 4;
        int n = matchsticks.size();
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        if(matchsticks[0] > target) return false;

        int M = 1<<n;
        vector<int> dp(M, -1);
        dp[0] = 0;
        for(int mask=0; mask<M; ++mask){
            if(dp[mask] == -1) continue;
            for(int i=0;i<n;i++){
                if(!(mask & (1<<i))){
                    if(dp[mask] + matchsticks[i] <= target){
                        int nxt = mask | (1<<i);
                        int val = (dp[mask] + matchsticks[i]) % target;
                        if(dp[nxt] == -1) dp[nxt] = val;
                    }
                }
            }
        }
        return dp[M-1] == 0;
    }
};