题单介绍：
精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。
目录
题单介绍：
题目：437. 路径总和 III - 力扣（Leetcode）
题目的接口：
解题思路：
代码：
过过过过啦！！！！
题目：416. 分割等和子集 - 力扣（Leetcode）
题目的接口：
解题思路：
代码：
过过过过啦！！！！
写在最后：
题目：437. 路径总和 III - 力扣（Leetcode）
题目的接口：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int pathSum(TreeNode* root, int targetSum) { } };
解题思路：
这道题的做法，我就是直接使用深度优先搜索，
然后通过rootSum函数查找路径和，
通过重复调用pathSum自身来查找不同根节点的路径和，
核心在于通过每次调用rootSum的时候减少targetSum的方式完成路径求和。
代码如下：
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: long pathSum(TreeNode* root, long targetSum) { if(root == nullptr) return 0; long ret = rootSum(root, targetSum); ret += pathSum(root->left, targetSum); ret += pathSum(root->right, targetSum); return ret; } private: long rootSum(TreeNode* root, long targetSum) { if(root == nullptr) return 0; long ret = 0; if(root->val == targetSum) ret++; ret += rootSum(root->left, targetSum - root->val); ret += rootSum(root->right, targetSum - root->val); return ret; } };
过过过过啦！！！！
题目：416. 分割等和子集 - 力扣（Leetcode）
题目的接口：
class Solution { public: bool canPartition(vector& nums) { } };
解题思路：
这道题的正统解法应该是动态规划，
但是我不会动态规划，然后我就在讨论区看到了一个另类的解法，
具体思路是这样的：
因为是分成两个子集，且都是整数，所以他们的和其实就是总和的一半，
把所有相加的情况都跟总和的一半作比较，然后就能得出能否分成两个子集了，
代码如下：
代码：
class Solution { public: bool canPartition(vector& nums) { int sum = 0; for(auto e : nums) sum += e; if(sum % 2 != 0) return false; int target = sum / 2; set st; for(int i = 0; i < nums.size(); i++) { set snum; if(nums[i] == target) return true; if(nums[i] < target) snum.insert(nums[i]); for(auto num : st) { int tarSum = nums[i] + num; if(tarSum == target) return true; if(tarSum < target) snum.insert(tarSum); } for(auto k : snum) st.insert(k); } return false; } };
过过过过啦！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
