Day 29

I use C++, forgive me for the mistake. The article was meant to urge me to learn. I would be very happy if it happened to help you.

I. 39. Combination Sum

Give you an array of integers with no duplicate elements, candidates, and a target integer target, find all the different combinations in candidates that can make numbers and target numbers target, and return them as a list. You can return these combinations in any order.

The same number in candidates can be selected repeatedly without restriction. If at least one number is selected differently, the two combinations are different.

For a given input, the number of different combinations guaranteed and target ed is less than 150.

Source: LeetCode
Links: https://leetcode-cn.com/problems/combination-sum
Copyright shall be owned by the withholding network. For commercial reprinting, please contact the official authorization. For non-commercial reprinting, please indicate the source.

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);//No Selection
        if (target - candidates[cur] >= 0){//Judgement Selection
            stk.push_back(candidates[cur]);
            dfs(candidates, cur, target - candidates[cur]);
            stk.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //As with previous permutations and combinations, each number has two choices, the selected number and the target
        //sort(candidates.begin(), candidates.end());
        //stk.resize(candidates.size());
        dfs(candidates, 0, target);
        return ans;
    }
};

2.40. Combination Sum II

Given a set of candidates with a candidate number and a target number, find all combinations of candidates that can make numbers and targets.

Each number in candidates can only be used once in each combination.

Note: Unset cannot contain duplicate combinations.

Source: LeetCode
Links: https://leetcode-cn.com/problems/combination-sum-ii
Copyright shall be owned by the withholding network. For commercial reprinting, please contact the official authorization. For non-commercial reprinting, please indicate the source.

class Solution {
public:
    vector<vector<int>> ans;
    vector<pair<int, int>> freq;//hash to record key values and numbers
    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);//Don't Select
        int most = min(target / freq[cur].first, freq[cur].second);//This step takes out the number, because it needs to be general, so adding min utes is worth learning.
        for (int i = 1; i <= most; ++i){
            stk.push_back(freq[cur].first);//Multiple identical number of one-time operations
            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) {
        //Every digital intelligence is used once here, and there are many things to learn about this topic
        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;

    }
};

3. 17. Letter Combination of Phone Numbers

Given a string containing only the numbers 2-9, return all the combinations of letters it can represent. Answers can be returned in any order.

Give the number-to-letter mapping as follows (same as the phone key). Note that 1 does not correspond to any letter.

Source: LeetCode
Links: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
Copyright shall be owned by the withholding network. For commercial reprinting, please contact the official authorization. For non-commercial reprinting, please indicate the source.

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

Notice the definition of recursive variables for arrays and strings