枚举子集，复杂度为 。通常要预处理出某个子集对应的性质，比如和、max-min之类

for (int i = t; i; i = i - 1 & t) {

}
// 补集
int t = j ^ ((1 << m) - 1);

---

LC1655.分配重复整数

经典子集状压DP，自己写出了正确代码，转移部分类似背包，一维时要从大到小枚举

class Solution {
public:
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        unordered_map<int, int> mp;
        for (int x: nums) mp[x] ++;
        vector<int> freq;
        for (auto& [_, x]: mp) freq.push_back(x);
        int n = freq.size(), m = quantity.size();

        vector<int> g(1 << m, 0);
        for (int i = 1; i < 1 << m; i++)
            for (int j = 0; j < m; j++) 
                if (i >> j & 1) g[i] += quantity[j];

        bool f[1 << m];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = (1 << m) - 1; j; j--)
                for (int k = j; k; k = k - 1 & j)
                    if (g[k] <= freq[i]) f[j] |= f[j - k];

        return f[(1 << m) - 1];
    }
};

---

LC1681.最下不兼容性

也是子集状压DP，但这题的转移我们考虑一组一组转移，即枚举最后一组

class Solution {
public:
    // 暴力枚举 i 然后 j 是枚举 i 的所有子集
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size(), INF = 1e8;
        vector<int> f(1 << n, INF);
        vector<int> cost(1 << n);
        int d[16];
        f[0] = 0;
        for (int i = 1; i < 1 << n; i++)
        {
            cost[i] = -1;
            if (__builtin_popcount(i) == n / k)
            {
                int cnt = 0;
                for (int j = 0; j < n; j++)
                    if (i >> j & 1) d[cnt ++] = nums[j];
                sort(d, d + cnt);
                int flag = 1, mn = d[0], mx = d[0];
                for (int j = 1; j < cnt; j++)
                {
                    if (d[j] == d[j - 1])
                    {
                        flag = 0;
                        break;
                    }
                    mn = min(mn, d[j]), mx = max(mx, d[j]);
                }
                if (flag) cost[i] = mx - mn;
            }
        }

        for (int i = 1; i < 1 << n; i++)
        {
            if (__builtin_popcount(i) % (n / k)) continue; // 剪枝
            for (int j = i; j; j = j - 1 & i)
                if (cost[j] != -1) 
                    f[i] = min(f[i], f[i - j] + cost[j]);
        }   
        
        return f[(1 << n) - 1] == INF ? -1 : f[(1 << n) - 1];
    }
};

---

枚举固定大小的子集：Gosper's Hack

它是一种生成 元集合所有 元子集的算法：

void GospersHack(int k, int n)
{
	int cur = (1 << k) - 1;
    int limit = (1 << n);
    while (cur < limit)
    {
        int lb = cur & -cur; // lowbit
        int left = cur + lb;
        int right = (cur ^ (cur + lb)) >> __builtin_ctz(lb) + 2;
        cur = left | right;
    }
}

例题为：

LC2397.被列覆盖的最多行数

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int n = matrix.size(), m = matrix[0].size();
        int row[n];
        memset(row, 0, sizeof row);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j]) row[i] |= (1 << j);
        int res = 0;
        int cur = (1 << numSelect) - 1, limit = 1 << m;
        while (cur < limit)
        {
            int cnt = 0;
            for (int i = 0; i < n; i++)
                if ((cur & row[i]) == row[i]) cnt ++;
            res = max(res, cnt);
            int lb = cur & -cur;
            int left = cur + lb;
            int right = (cur ^ left) >> __builtin_ctz(lb) + 2;
            cur = left | right; 
        }
        return res;
    }
};