LeetCode刷题 | Day 3 分割等和子集（Partition Equal Subset Sum）

本文主要是介绍LeetCode刷题 | Day 3 分割等和子集（Partition Equal Subset Sum），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode刷题 | Day 3 分割等和子集（Partition Equal Subset Sum）

---

---

前言

LeetCode位置：416. 分割等和子集

日常刷题，维持手感，同步学习英语，刷题顺序参考B站UP@justyyuk的系列视频，感兴趣的点波关注。
学海无涯，大路千万，感恩此程，彼此真诚陪伴！

Ps：第一次刷到的道友留步，这里拉齐一下信息。文章主要记录视频中的主要内容，算法思路会按照个人理解，用伪代码+举例每步输出的方式呈现。代码部分会以Python和C++语法进行呈现。文章最后会总结一些英语词汇。OK，就啰嗦这么多，开始进步[干杯🐱‍👓]

---

一、题目概述

输入：nums列表
输出：bool值，表示原始列表是否存在和相等的两个子列表

PS：

1. 子序列 (Subsequence/Subset):

   • 子序列是通过从原始序列中删除一些或不删除任何元素且不改变剩余元素顺序而得到的序列。
   • 例子：对于序列 [1, 2, 3, 4]，[1, 3, 4] 和 [2, 4] 是子序列。
   • 注意：[1, 4, 3] 不是 子序列，因为顺序改变了。

2. 子列表 (Sublist)

   • 子列表是列表的连续部分，意味着元素必须是连续的。
   • 例子：对于列表 [1, 2, 3, 4]，[2, 3] 和 [1, 2, 3]是子列表。
   • 注意：[1, 3] 不是 子列表，因为它不是连续的。

3. 子数组 (Subarray):

   • 类似于子列表，子数组是数组的连续部分。
   • 例子：对于数组 [1, 2, 3, 4]，[2, 3] 和 [1, 2, 3] 是子数组。
   • 注意：[1, 3] 不是 子数组，因为它不是连续的。

• 在许多情况下，当数据结构是数组或列表时，“子列表”和“子数组”可以互换使用，但“子数组”一词专门用于数组。

二、解题方法

2.1 动态规划思想

2.1.1 思路讲解

Ps： 动态规划（Dynamic Programming）特征
- 最优子结构：
- 动态规划要求问题具有最优子结构性质，即问题的最优解包含其子问题的最优解。
- 重叠子问题：
- 动态规划需要问题具有重叠子问题性质，即不同的子问题在求解时会重复出现。
- 状态转移方程：
- 动态规划通过状态转移方程将问题分解为子问题，并通过子问题的解来推导原问题的解。
- 全局最优解：
- 动态规划通过考察所有可能的子问题组合来确保找到全局最优解。
- 记忆化或表格法：
- 动态规划通常使用记忆化搜索或自底向上的表格法来避免重复计算。

• 动态规划策略

  • 本题思路主要是通过递归的方式遍历到任意一个数组的全部子序列，然后在遍历的过程中判断当前子序列是否满足和为原数组一半的条件。

• 具体步骤

  1. 求和与奇偶性检查:

     • 先计算数组 nums 的总和 total。 如果 total 是奇数，则不可能将数组分成两个和相等的子集，因为奇数不能被均分，所以直接返回False。 如果 total 是偶数，那么我们需要找到一个子集，其和为 total // 2，称之为 half。

  2. 递归与缓存:

     • 定义一个递归函数 dp(i, s)，表示在考虑前 i 个元素的情况下，是否可以得到和为 s 的子集。

  3. 利用 Python 的 @cache

     • 装饰器（或者等价的 functools.lru_cache）来缓存递归结果，避免重复计算，提高效率。

  4. 递归的边界条件与状态转移:

这篇关于LeetCode刷题 | Day 3 分割等和子集（Partition Equal Subset Sum）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---