本文涉及知识点

反证法 决策包容性 位运算、状态压缩、枚举子集汇总

LeetCode2732. 找到矩阵中的好子集

给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。
从原矩阵中选出若干行构成一个行的 非空 子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。
更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。
请你返回一个整数数组，它包含好子集的行下标，请你将子集中的元素 升序 返回。
如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。
一个矩阵 grid 的行 子集 ，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。
示例 1：
输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释：我们可以选择第 0 和第 1 行构成一个好子集。
选出来的子集大小为 2 。

• 第 0 列的和为 0 + 0 = 0 ，小于等于子集大小的一半。
• 第 1 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
• 第 2 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
• 第 3 列的和为 0 + 1 = 1 ，小于等于子集大小的一半。
  示例 2：
  输入：grid = [[0]]
  输出：[0]
  解释：我们可以选择第 0 行构成一个好子集。
  选出来的子集大小为 1 。
• 第 0 列的和为 0 ，小于等于子集大小的一半。
  示例 3：
  输入：grid = [[1,1,1],[1,1,1]]
  输出：[]
  解释：没有办法得到一个好子集。
  提示：
  m == grid.length
  n == grid[i].length
  1 <= m <= 10⁴
  1 <= n <= 5
  grid[i][j] 要么是 0 ，要么是 1 。

决策包容性+反证法

假定某个合法解是选择k行。
性质一：k是奇数，且k >1,则一定存在k-1行的合法解。利用决策包容性来证明。则任意删除一行。 任意一列的和变小或不边。floor(k/2)和floor((k-1)/2)相等。
性质二：k是偶数,且k>2，一定存在k-2的合法解。利用反证法证明。从中任意选择k-2行，如果非法，则说某列，这k-2包括k/2个1。$\to$ 此列其它行全部为0 $\to$ 除了选择这k-2行，选择其它k-2，此列都合法。
C k k − 2 = C k 2 = k × ( k − 2 ) / 2 C_{k}^{k-2}=C_{k}^2=k\times(k-2)/2 Ckk−2​=Ck2​=k×(k−2)/2 ,显然随着k递增而递增。k取最小值4，结果为6。即至少有6个不同列，和总共只有5列矛盾。
性质三：结合性质一性质二，如果k>=2，一定存在合法的2行解。
性质四:如果某行全为0，则可以只选择此行。

状态压缩

每行最多5列，值只能是0或1。可以用5位二进制的正数表示。
空间复杂度：O(2ⁿ)
如果不用子集状态压缩：
时间复杂度：O(2ⁿ2ⁿm)
如果用子集状态压缩：
时间复杂度：O(3ⁿm)

2024年11月23号补充

一，k == 4。分成6组，A1 = {0,1},B1 = {2,3} ;A2 = {0,2},B2={1,3} ;A3 = {0,3},B3={1,2}。这六组，如果都不符合本题，说明有6列，某两行之和为2。这6列不会相同，否则此列之和>=3，与和<=2矛盾。
二，k = = 6。方案一：A1 = {0,1} ,其它行B1;A2={2,3},其它行B2;A3={4,5}，其它B3。总共只有只有5列，故A1和A2、A3至少一个只有一列和为0。不失一般性，令为A1，且第一列和是0，A1的第二列和是2。
B1有三行第1列是1,任意一行与A1的任意一行交换（交换一），则第一列和第二列符合。如果A1剩下的三位是：000 111，则交换000后，B1符合题设。如果是001 110。从交换一的3行中找一个第5列为1的换001。3行的第5列不可能全部是0，否则加上A1的0就是4，与假设矛盾。如果A1有多列的和为2，任意交换皆可。
总结：
假设一：能找到两行，只有一列之和为2。
证明：共2m行，令此两行为A，余下的为B。令A的第一列和为2，第二列和为0。余下的3列顶多3列和为1。A的两行一定有一行顶多一列为1，令此列是第一行三列。B中有m行，第二列为1，中m行中一定有一行，第三列为1，令此行是第三行。将第三行和第一行交换后，B就符合假设。
证明假设一：任何两行，是组合，不是排列。共有x= C 2 m 2 C_{2m}^2 C2m2​中选法。任意一列两行和为2的选法数量：y = C m 2 C_{m}^2 Cm2​。
如果任意选法都至少2列和为2,则
$$2x<=5y\to 4m\times (2m-1)/2<=5m\times (m-1)/2\to 8m-4<=5m-5\to 3m<=-1$$
本题m>=1，估计不存在3m <=-1。
得证。

代码

核心代码

class Solution {
public:
	vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
		const int N = grid[0].size();
		const int iMaskCount = 1 << N;
		int i = -1;
		vector<int> maskRow(iMaskCount,-1);
		for (const auto& v : grid) {
			i++;
			int mask = 0;
			for (const auto& n: v) {
				mask = mask * 2 + n;
			}
			if (0 == mask) { return { i }; }
			const int can = (~mask) & (iMaskCount - 1);
			for (int sub = can; sub; sub = (sub - 1) & can) {
				if (-1 != maskRow[sub]) {
					return { maskRow[sub],i };
				}
			}
			maskRow[mask] = i;
		}
		return {};
	}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	vector<vector<int>> grid;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			grid = { {0,1,1,0},{0,0,0,1},{1,1,1,1} };
			auto res = Solution().goodSubsetofBinaryMatrix(grid);
			AssertEx(vector<int>{0, 1}, res);
		}
		TEST_METHOD(TestMethod1)
		{
			grid = { {0} };
			auto res = Solution().goodSubsetofBinaryMatrix(grid);
			AssertEx(vector<int>{0}, res);
		}
		TEST_METHOD(TestMethod2)
		{
			grid = { {1,1,1},{1,1,1} };
			auto res = Solution().goodSubsetofBinaryMatrix(grid);
			AssertEx(vector<int>{}, res);
		}
	};
}