淮北公司做网站,菏泽网站建设菏泽,顺德中小企业网站建设,公共资源交易中心归哪个部门管目录 77. 组合题目描述题解 216. 组合总和 III题目描述题解 17. 电话号码的字母组合题目描述题解 77. 组合
点此跳转题目链接
题目描述
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1#xff1a;
输… 目录 77. 组合题目描述题解 216. 组合总和 III题目描述题解 17. 电话号码的字母组合题目描述题解 77. 组合
点此跳转题目链接
题目描述
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2
输入n 1, k 1
输出[[1]]提示
1 n 201 k n
题解
参考代码随想录-77.组合 讲得非常细了。
算是回溯算法的入门题目核心要理解回溯的树形结构以及其中的横向和纵向遍历逻辑 然后考虑回溯三部曲 ✨
1️⃣ 处理
本题就是很基础的求组合所以每次往当前组合 path 添加新数字就好了
path.push_back(i); 当前组合名称取为 path 旨在呼应回溯树形结构图中的纵向“探索”路线先取一个数x再取一个数y 2️⃣ 递归
递归出口是经典的——当前组合大小达到目标组合大小则将其加入结果集
if (path.size() k)
{res.push_back(path);return;
}否则当前位置数字确定后递归下一个位置的数来做组合
backTracking(i 1, end, k)3️⃣ 回溯
弹出当前组合的最后一个值以便探索该位置的其他可能值
path.pop_back(); 整体代码如下
C
class Solution
{
private:vectorint path;vectorvectorint res;public:void backTracking(int start, int end, int k){// 回溯出口子结果path已满纵向遍历if (path.size() k){res.push_back(path);return;}// 横向遍历for (int i start; i end; i){path.push_back(i); // 处理backTracking(i 1, end, k); // 递归path.pop_back(); // 回溯}}vectorvectorint combine(int n, int k){backTracking(1, n, k);return res;}
};Go
type Helper struct {path []intres [][]int
}func (helper *Helper) backTracking(start int, end int, k int) {// 递归出口if len(helper.path) k {// newPath : make([]int, len(helper.path))// copy(newPath, helper.path)// helper.res append(helper.res, newPath)helper.res append(helper.res, append([]int(nil), helper.path...))return}// 横向遍历for i : start; i end; i {helper.path append(helper.path, i) // 处理helper.backTracking(i1, end, k) // 递归helper.path helper.path[:len(helper.path)-1] // 回溯}
}func combine(n int, k int) [][]int {helper : Helper{}helper.backTracking(1, n, k)return helper.res
}216. 组合总和 III
点此跳转题目链接
题目描述
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。示例 2:
输入: k 3, n 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 2 6 9
1 3 5 9
2 3 4 9
没有其他符合的组合了。示例 3:
输入: k 4, n 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。提示:
2 k 91 n 60
题解 参考代码随想录-216 回溯算法解决。首先想清楚回溯的树形结构图 然后走回溯三部曲 ✨ 处理 将当前处理的数字加入当前组合 path 并求此时组合中的数字和 进行这一步之前可以剪枝由于是从1到9从小到大横向遍历如果 目标和 与 当前和 的差小于即将加入的数字说明再加数字必将导致组合总和过大故没必要在此基础上往后遍历处理了。 递归 递归地尝试将后面的数字加入组合递归出口 path 的大小达到目标大小 k 且其中数字和等于目标和则将 path 加入结果集 回溯 弹出当前组合的最后一个数以便探索该位置放其他数的可能
代码如下
class Solution
{
private:vectorint path;vectorvectorint res;public:void backTracking(int start, int end, int maxPathSize, int targetSum, int curSum){// 递归出口纵向遍历if (path.size() maxPathSize){if (curSum targetSum)res.push_back(path);return;}// 剪枝if (targetSum - curSum start)return;// 横向遍历for (int i start; i end; i){curSum i;path.push_back(i); // 处理backTracking(i 1, end, maxPathSize, targetSum, curSum); // 递归curSum - i;path.pop_back(); // 回溯}}vectorvectorint combinationSum3(int k, int n){backTracking(1, 9, k, n, 0);return res;}
};17. 电话号码的字母组合
点此跳转题目链接
题目描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
题解 参考代码随想录-17 回溯算法解决。首先想清楚回溯的树形结构图 然后走回溯三部曲 ✨ 处理 从当前处理的数字对应的字母串中取一个字母加入当前组合字符串 path 递归 递归地尝试将后面的数字对应的可能字母加入组合递归出口 path 的长度与所给数字串 digits 相同则将 path 加入结果集 回溯 弹出当前组合的最后一个字符以便探索该位置放其他字母的可能
c代码如下
class Solution
{
private:string path ;vectorstring res;unordered_mapchar, string dict {{2, abc},{3, def},{4, ghi},{5, jkl},{6, mno},{7, pqrs},{8, tuv},{9, wxyz}};public:void backTracking(const string digits, int start){// 递归出口if (path.length() digits.length()){res.push_back(path);return;}char digit digits[start]; // 当前要处理的数字string letters dict[digit]; // 当前处理数字对应的字母// 横向遍历for (int i 0; i letters.length(); i){path.push_back(letters[i]); // 处理backTracking(digits, start 1); // 递归path.pop_back(); // 回溯}}vectorstring letterCombinations(string digits){if (digits )return res;backTracking(digits, 0);return res;}
};顺便再熟悉下golang
type Helper struct {path stringres []stringdict map[byte]string
}func newHelper() *Helper {return Helper{dict: map[byte]string{2: abc,3: def,4: ghi,5: jkl,6: mno,7: pqrs,8: tuv,9: wxyz,},}
}func (helper *Helper) backTracking(digits string, start int) {// 递归出口if len(helper.path) len(digits) {helper.res append(helper.res, helper.path)return}letters : helper.dict[digits[start]]for _, letter : range letters {helper.path helper.path string(letter) // 处理helper.backTracking(digits, start1) // 递归helper.path helper.path[:len(helper.path)-1] // 回溯}
}func letterCombinations(digits string) []string {helper : newHelper()if len(digits) 0 {return helper.res}helper.backTracking(digits, 0)return helper.res
}
