组合问题 中等🌟🌟🌟🌟🌟
课后作业
问题描述
原文链接：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 <= 20
1 <= k <= n
代码实现
Java
class Solution {
// 创建存放结果集
List<List<Integer>> res = new ArrayList<>();
// 存放单个子集
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTrace(n, k , 1);
return res;
}
void backTrace(int n, int k, int index){
// 优化：称之为剪枝
if(temp.size() + (n - index + 1) < k){
return;
}
// 结束条件
if(temp.size() == k){
res.add(new ArrayList<>(temp));
return;
}
// 从多个元素中逐一选择
for(int i = index; i <= n; i++){
// 选元素进行处理
temp.add(i);
// 继续下一层
backTrace(n, k, i + 1);
// 撤销
temp.remove(temp.size() - 1);
}
}
}
Python
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
# 创建存放结果集
res = []
# 存放单个子集
temp = []
def backTrace(n, k, index):
# 优化：称之为剪枝
if len(temp) + (n - index + 1) < k:
return
# 结束条件
if len(temp) == k:
res.append(list(temp))
return
# 从多个元素中逐一选择
for i in range(index, n + 1):
# 选元素进行处理
temp.append(i)
# 继续下一层
backTrace(n, k, i + 1)
# 撤销
temp.pop()
backTrace(n, k, 1)
return res
C++
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
// 创建存放结果集
vector<vector<int>> res;
// 存放单个子集
vector<int> temp;
function<void(int, int, int)> backTrace = [&](int n, int k, int index) {
// 优化：称之为剪枝
if (temp.size() + (n - index + 1) < k) {
return;
}
// 结束条件
if (temp.size() == k) {
res.push_back(temp);
return;
}
// 从多个元素中逐一选择
for (int i = index; i <= n; i++) {
// 选元素进行处理
temp.push_back(i);
// 继续下一层
backTrace(n, k, i + 1);
// 撤销
temp.pop_back();
}
};
backTrace(n, k, 1);
return res;
}
};