# 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

```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

```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

```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

Keywords: Algorithm leetcode

Added by tipjones on Thu, 03 Feb 2022 21:23:42 +0200