1、分割等和子集

给定一个只包含正数的非空数组，是否可以把数组分为两个子集，且两个子集元素和相等

思路：其实这道题就是判断给定数组是否是偶数，且子集的值可不可以等于总和的一半

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(auto&e:nums){sum += e;}sort(nums.begin(),nums.end(),greater<int>());if((sum % 2) != 0){return false;}if(nums[0] > sum /2){return false;}bool ans = dfs(nums, 0, 0, sum/2);if(ans){return true;}return false;}bool dfs(vector<int>&nums,int ptr,int cur,int target){int remain = target - cur;for(int i = ptr;i<nums.size();++i){if(nums[i] == remain){return true;}else if(nums[i] < remain){if(dfs(nums,i+1,cur+nums[i],target)){return true;}}}return false;}
};

2、二叉树的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径

示例:
给定如下二叉树，以及目标和 sum = 22

返回:
[
[5,4,11,2],
[5,8,4,5]
]

参考代码

class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int sum) {dfs(root,sum,0);return res;}void dfs(TreeNode* root, int sum,int cur){if(root == nullptr){return;}path.push_back(root->val);cur+=root->val;if(root->left == nullptr && root->right == nullptr\&& sum == cur){res.push_back(path);}dfs(root->left,sum,cur);dfs(root->right,sum,cur);path.pop_back();}
private:vector<vector<int>>res;vector<int>path;
};

3、电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

回溯法

class Solution {
public:unordered_map<char,string>um{{'0'," "},{'1',"*"},{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};vector<string> letterCombinations(string digits) {vector<string>res;if(digits == ""){return res;}dfs(res,"",digits,0);return res;}void dfs(vector<string>&res,string str,\string& digits,int k){// 满足条件则进行插入返回      if(str.size() == digits.size()){res.push_back(str);return;}// 取出对应的字符串.string temp = um[digits[k]];for(char e:temp){str +=e;dfs(res,str,digits,k+1);str.pop_back();}return;}
};