第二十九天

我使用的C++，错误的地方请见谅，文章初衷仅用来督促本人学习，如果恰巧能够给你带来帮助，我会十分开心。

一、39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:vector<vector<int>> ans;vector<int> stk;void dfs (vector<int>& candidates, int cur, int target){if (cur == candidates.size()){return;}if (target == 0){ans.push_back(stk);return;}dfs(candidates, cur + 1, target);//不选择if (target - candidates[cur] >= 0){//判断选择stk.push_back(candidates[cur]);dfs(candidates, cur, target - candidates[cur]);stk.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {//和之前排列组合一样，每个数都有选与不选两种选择，选取的数做和与target做比较//sort(candidates.begin(), candidates.end());//stk.resize(candidates.size());dfs(candidates, 0, target);return ans;}
};

二、40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:vector<vector<int>> ans;vector<pair<int, int>> freq;//hash来记录键值与个数vector<int> stk;void dfs (int cur, int target){if (target == 0){ans.push_back(stk);return;}if (cur == freq.size() || target < freq[cur].first){return;}dfs(cur + 1, target);//不选取int most = min(target / freq[cur].first, freq[cur].second);//这一步来取出个数，因为要具有一般性，所以加了min，很值得学习for (int i = 1; i <= most; ++i){stk.push_back(freq[cur].first);//多个相同的数一次性操作dfs(cur + 1, target - i * freq[cur].first);}for (int i = 1; i <= most; ++i){stk.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {//这里每一个数字智能用一次，这一题里有很多值得学习的地方sort(candidates.begin(), candidates.end());for (int num : candidates){if (freq.empty() || num != freq.back().first){freq.emplace_back(num, 1);}else {++freq.back().second;}}dfs(0, target);return ans;}
};

三、17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:vector<string> ans;string stk;vector<string> letterCombinations(string digits) {if (digits.empty()){return ans;}unordered_map <char, string> Map = {{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};back(0, Map, digits);return ans;}void back (int cur, const unordered_map<char, string>& Map, string& digits){if (cur == digits.size()){ans.push_back(stk);return;}else {char digit = digits[cur];const string& letters = Map.at(digit);for (auto  letter : letters){stk.push_back(letter);back(cur + 1, Map, digits);stk.pop_back();}}}
};

要注意数组和字符串的递归变量的定义