216. 組合總和 III
找出所有相加之和為 n 的 k 個數(shù)的組合,且滿足下列條件:
只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 奶赔。該列表不能包含相同的組合兩次,組合可以以任何順序返回输虱。
示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backTracking(int sum, int startIndex, int k, int target) {
//cout << sum << " " << path.size() << " " <<k <<endl;
if (path.size() == k && target == sum) {
result.emplace_back(path);
return;
}
if (path.size() >= k && target != sum) {
return;
}
if (sum > target && path.size() <= k) {
return;
}
for (int i = startIndex; i<= 9 - (k-path.size()) + 1; i++) {
path.emplace_back(i);
sum = sum + i;
//cout << sum << endl;
backTracking(sum, i+1, k, target);
sum = sum -i ;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
path.clear();
result.clear();
backTracking(0, 1, k, n);
return result;
}
};
知識點:
套用回溯法套路即可脂凶。主要要把圖畫出來宪睹。
for循環(huán)要干什么,每次進(jìn)入迭代要干什么蚕钦、
void backtracking(參數(shù)) {
if (終止條件) {
存放結(jié)果;
return;
}
for (選擇:本層集合中元素(樹中節(jié)點孩子的數(shù)量就是集合的大泻岜ぁ)) {
處理節(jié)點;
backtracking(路徑,選擇列表); // 遞歸
回溯冠桃,撤銷處理結(jié)果
}
}
17. 電話號碼的字母組合
給定一個僅包含數(shù)字 2-9
的字符串,返回所有它能表示的字母組合道宅。答案可以按 任意順序 返回食听。
給出數(shù)字到字母的映射如下(與電話按鍵相同)。注意 1 不對應(yīng)任何字母污茵。
200px-telephone-keypad2svg.png
示例 1:
輸入:digits = "23"
輸出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
class Solution {
private:
string path;
vector<string> result;
const string letterMap[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
void backTracking(string digits, int index) {
if (index == digits.size()) {
result.push_back(path);
return;
}
int digit = digits[index] - '0';
string letters = letterMap[digit];
# for循環(huán)遍歷的是每一層的數(shù)據(jù)
for (int i = 0 ; i< letters.size(); i++) {
path.push_back(letters[i]);
#迭代是進(jìn)入下一層的數(shù)據(jù)
backTracking(digits, index+1);
path.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
path.clear();
result.clear();
if (digits.size() == 0) {
return result;
}
backTracking(digits, 0);
return result;
}
};