import unittestfrom typing import Listdef canPartition(nums: List[int]) -> bool: """ 判断是否可以将数组分割成两个和相等的子集 参数: nums: 正整数数组 返回: bool: 如果可以分割返回True，否则返回False """ total_sum = sum(nums) # 如果总和为奇数，无法分割 if total_sum % 2 != 0: return False target = total_sum // 2 # 如果最大元素大于目标，无法分割 if max(nums) > target: return False # 初始化DP数组，dp[0]为True，其余为False dp = [False] * (target + 1) dp[0] = True # 遍历每个数字 for num in nums: # 从后往前更新，避免重复使用同一元素 for j in range(target, num - 1, -1): if dp[j - num]: dp[j] = True return dp[target]class TestCanPartition(unittest.TestCase): """测试分割等和子集算法""" def test_leetcode_example_1(self): """测试LeetCode示例1：可以分割""" nums = [1, 5, 11, 5] self.assertTrue(canPartition(nums)) # 可以分割成 [1,5,5] 和 [11] def test_leetcode_example_2(self): """测试LeetCode示例2：无法分割""" nums = [1, 2, 3, 5] self.assertFalse(canPartition(nums)) # 无法分割 def test_odd_sum(self): """测试总和为奇数的情况""" nums = [1, 2, 3, 4, 10] # 总和=20，是偶数，但需要检查是否能分割 # 先计算总和：1+2+3+4+10=20，偶数，所以继续检查 # 最大元素10=目标10，可以继续 # 实际可以分割：10+4+3+2+1=20？不对，应该是两个子集各为10 # 实际上：10+4+3+2+1=20，但需要分成两个和为10的子集 # 可能的分解：[10]和[1,2,3,4]（1+2+3+4=10） self.assertTrue(canPartition(nums)) # 真正总和为奇数的测试 nums_odd = [1, 2, 3, 4, 5] # 总和=15，奇数 self.assertFalse(canPartition(nums_odd)) def test_single_element(self): """测试单元素数组""" nums = [5] self.assertFalse(canPartition(nums)) # 只有一个元素，无法分成两个非空子集 def test_two_elements_equal(self): """测试两个相等元素""" nums = [5, 5] self.assertTrue(canPartition(nums)) # 可以分成 [5] 和 [5] def test_two_elements_unequal(self): """测试两个不相等元素""" nums = [3, 5] self.assertFalse(canPartition(nums)) # 无法分割 def test_large_element(self): """测试存在大元素的情况""" nums = [1, 3, 5, 7, 19] # 总和=35，19>35/2=17.5，但19>17.5，所以无法分割 self.assertFalse(canPartition(nums)) def test_all_same_elements(self): """测试所有元素相同""" nums = [2, 2, 2, 2, 2, 2] # 总和=12，目标=6，可以分成各为6的两个子集 self.assertTrue(canPartition(nums)) def test_complex_case_1(self): """测试复杂情况1：需要精确选择""" nums = [1, 2, 3, 4, 5, 6, 7] # 总和=28，目标=14 # 可以分割：1+6+7=14, 2+3+4+5=14 self.assertTrue(canPartition(nums)) def test_complex_case_2(self): """测试复杂情况2：无法精确分割""" nums = [1, 2, 3, 4, 5, 6, 8] # 总和=29，奇数，无法分割 self.assertFalse(canPartition(nums)) def test_with_zeros(self): """测试包含零的情况（虽然题目是正整数，但测试健壮性）""" nums = [0, 1, 2, 3] # 总和=6，目标=3，可以分割：0+3=3, 1+2=3 self.assertTrue(canPartition(nums)) def test_minimum_constraints(self): """测试题目约束的最小值""" nums = [1] # 最小数组长度1 self.assertFalse(canPartition(nums)) def test_maximum_constraints(self): """测试题目约束的最大值""" # 创建一个满足条件的数组：总和为偶数，可以分割 nums = [1] * 200 # 200个1，总和=200，目标=100 self.assertTrue(canPartition(nums)) # 创建一个不满足条件的数组：总和为奇数 nums_odd = [1] * 199 # 199个1，总和=199，奇数 self.assertFalse(canPartition(nums_odd)) def test_algorithm_correctness(self): """验证算法正确性（多种情况对比）""" test_cases = [ ([1, 5, 11, 5], True, "LeetCode示例1"), ([1, 2, 3, 5], False, "LeetCode示例2"), ([1, 1], True, "两个相同元素"), ([1, 2], False, "两个不同元素"), ([1, 2, 3, 4, 5, 6, 7], True, "复杂可分割"), ([1, 3, 4, 8], False, "无法精确分割"), ] for nums, expected, description in test_cases: with self.subTest(nums=nums, description=description): actual = canPartition(nums) self.assertEqual(actual, expected)class TestCanPartitionPropertyBased(unittest.TestCase): """基于属性的测试""" def test_symmetry_property(self): """测试对称性：结果应独立于数组顺序""" nums1 = [1, 5, 11, 5] nums2 = [5, 1, 5, 11] # 相同元素，不同顺序 self.assertEqual(canPartition(nums1), canPartition(nums2)) def test_duplicate_elements(self): """测试重复元素处理""" nums1 = [1, 5, 11, 5] nums2 = [1, 5, 5, 11] # 相同元素，顺序不同 self.assertEqual(canPartition(nums1), canPartition(nums2))def run_comprehensive_test_suite(): """运行全面的测试套件并生成详细报告""" # 创建测试加载器 loader = unittest.TestLoader() # 创建测试套件 suite = unittest.TestSuite() suite.addTests(loader.loadTestsFromTestCase(TestCanPartition)) suite.addTests(loader.loadTestsFromTestCase(TestCanPartitionPropertyBased)) # 运行测试 runner = unittest.TextTestRunner(verbosity=2) result = runner.run(suite) # 生成测试报告 print("\n" + "="*70) print("分割等和子集算法测试报告") print("="*70) print(f"运行测试数: {result.testsRun}") print(f"失败数: {len(result.failures)}") print(f"错误数: {len(result.errors)}") if result.wasSuccessful(): print("🎉 所有测试通过！算法实现正确。") # 显示关键测试用例验证 print("\n关键测试用例验证:") key_test_cases = [ ([1, 5, 11, 5], True, "LeetCode示例1"), ([1, 2, 3, 5], False, "LeetCode示例2"), ([1, 1], True, "两个相同元素"), ([1, 3, 5], False, "奇数总和"), ] for nums, expected, description in key_test_cases: actual = canPartition(nums) status = "✅" if actual == expected else "❌" print(f"{description:15} | 输入: {nums}") print(f"{' ':15} | 输出: {actual} (期望: {expected}) {status}") print("-" * 50) else: print("❌ 有测试失败，请检查算法实现。") # 输出失败详情 for test, traceback in result.failures + result.errors: print(f"\n失败测试: {test}") print(f"错误信息:\n{traceback}") return result.wasSuccessful()if __name__ == '__main__': # 运行全面测试 success = run_comprehensive_test_suite() # 退出代码 exit(0 if success else 1)
