leetcode 77. Combinations 组合(中等)
LeetCode 组合 中等 77
2023-09-11 14:22:52 时间
一、题目大意
标签: 搜索
https://leetcode.cn/problems/combinations
给定两个整数 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 <= 20
- 1 <= k <= n
二、解题思路
用回溯方法解决组合问题,类似排列,排列回溯的是交换的位置,而组合回溯的是否把当前的数字加入结果中。
三、解题方法
3.1 Java实现
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
backTracking(ans, new int[k], 0, 1, n, k);
return ans;
}
void backTracking(List<List<Integer>> ans, int[] comb, int count, int pos, int n, int k) {
if (count == k) {
ans.add(Arrays.stream(comb).boxed().collect(Collectors.toList()));
return;
}
for (int i = pos; i <= n; i++) {
// 修改当前节点状态
comb[count++] = i;
// 递归子节点
backTracking(ans, comb, count, i + 1, n, k);
// 回改当前节点状态
count--;
}
}
}
四、总结小记
- 2022/6/4 好吃的东西很多,要克制
相关文章
- Java实现 LeetCode 674 最长连续递增序列(暴力)
- Java实现 LeetCode 491递增子序列
- Java实现 LeetCode 377 组合总和 Ⅳ
- Java实现 LeetCode 347 前 K 个高频元素
- Java实现 LeetCode 226 翻转二叉树
- SQK Server实现 LeetCode 175 组合两个表
- Java实现 LeetCode 117 填充每个节点的下一个右侧节点指针 II(二)
- Java实现 LeetCode 77 组合
- Java实现 LeetCode 39 组合总和
- LeetCode(77):组合
- LeetCode(40):组合总和 II
- leetcode 40. 组合总和 II---回溯篇3
- leetcode 120. 三角形最小路径和
- LeetCode - 2134 最少交换次数来组合所有的 1 II
- leetcode 617. Merge Two Binary Trees
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 430. 扁平化多级双向链表
- LeetCode 83. 删除排序链表中的重复元素
- 【28】实现 strStr()【LeetCode】