算法训练day28 LeetCode 216.17.
216.组合总和III
题目
题解
-
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(int targetSum, int k, int sum, int startIndex) { if (path.size() == k) { if (sum == targetSum) result.push_back(path); return; } for (int i = startIndex; i <= 9; i++) { sum += i; path.push_back(i); backtracking(targetSum, k, sum, i + 1); sum -= i; path.pop_back(); } } public: vector<vector<int>> combinationSum3(int k, int n) { result.clear(); path.clear(); backtracking(n, k, 0, 1); return result; } };
-
和77.十分类似,只需要添加一个总和等于n的约束条件。
17.电话号码的字母组合
题目
题解
-
递归地想,只按两个是最简单的情况
-
class Solution { private: const string letterMap[10] = { "", // 0 "", // 1 "abc", // 2 "def", // 3 "ghi", // 4 "jkl", // 5 "mno", // 6 "pqrs", // 7 "tuv", // 8 "wxyz", // 9 }; vector<string> result; // 所有结果集合 string s; // 单个结果 void backtracking(const string &digits, int index) { if (index == digits.size()) // 终止条件,完成一次组合,存放结果 { result.push_back(s); return; } int digit = digits[index] - '0'; // 将字符转换成int string letters = letterMap[digit]; // 通过上一步int选择对应字符集 for (int i = 0; i < letters.size(); i++) { s.push_back(letters[i]); // 处理 backtracking(digits, index + 1); // 递归,在下一个字符集中组合 s.pop_back(); // 回溯 } } public: vector<string> letterCombinations(string digits) { s.clear(); result.clear(); if (digits.size() == 0) { return result; } backtracking(digits, 0); return result; } };
-
以树形的结构组织组合的字符集,递归、处理、回溯。