目录
17 电话号码的字母组合
class Solution {
private:
vector<string>res;
const string strs[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
vector<string> letterCombinations(string digits) {
if(digits.size() == 0)return res;
getCombinations(digits,0,"");
return res;
}
void getCombinations(string digits,int cnt,string s){
if(cnt == digits.size()){
res.push_back(s);
return;
}
int digit = digits[cnt] - '0';
string str = strs[digit];
for(int i = 0;i < str.size();i++){
getCombinations(digits,cnt + 1,s + str[i]);
}
}
};时间复杂度O(×
)N是对应三个字母的数字个数,M是对应四个字母的数字个数
空间复杂度O(×
)N是对应三个字母的数字个数,M是对应四个字母的数字个数
216 组合总和 |||
class Solution {
private:
vector<vector<int>>res;
vector<int>now;
public:
vector<vector<int>> combinationSum3(int k, int n) {
dfs(1,0,k,n);
return res;
}
void dfs(int cnt,int sum,int k,int n){
if(sum > n)return;
if(now.size() == k){
if(sum == n)res.push_back(now);
return;
}
for(int i = cnt;i <= 9;i++){
now.push_back(i);
sum += i;
dfs(i + 1,sum,k,n);
sum -= i;
now.pop_back();
}
}
};时间复杂度O(N × )N为集合的大小，本题中为9，一个有
个状态(选择或者不选这个数字)
空间复杂度O(N)
