第二十九天

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

文章目录

• 第二十九天
• 一、39. 组合总和
• 二、40. 组合总和 II
• 三、17. 电话号码的字母组合

一、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();
            }
        }
    }
};

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