我是靠谱客的博主 热心铅笔，最近开发中收集的这篇文章主要介绍【算法leetcode每日一练】剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合：样例 1：样例 2：提示：分析题解原题传送门：https://leetcode-cn.com/problems/uUsW3B/原题传送门：https://leetcode-cn.com/problems/combinations/，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
文章目录
- 剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合：
- 样例 1：
- 样例 2：
- 提示：
- 分析
- 题解
- java
- c
- c++
- python
- go
- rust
- javascript
- typescript
- 原题传送门：https://leetcode-cn.com/problems/uUsW3B/
- 原题传送门：https://leetcode-cn.com/problems/combinations/
剑指 Offer II 080. 含有 k 个元素的组合 | 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
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 穷举所有组合，使用递归大法是最直观的。
- 每个数字都可以选择或者不选择。
- 由于是组合不是排列，所以我们可以从小到大取数，那第一位取数范围就是从1到n+1-k，第二位就是从2到n+2-k，第三位就是从3到n+3-k…
题解
java
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
this.dfs(ans, new Integer[k], 0, 1, n, k);
return ans;
}
/**
*
* @param ans 最终结果
* @param row 行记录
* @param rowSize 行数字数量
* @param s 开始数字
* @param n
* @param k
*/
private void dfs(List<List<Integer>> ans, Integer[] row, int rowSize, int s, int n, int k) {
if (rowSize == k) {
ans.add(Arrays.asList(Arrays.copyOf(row, row.length)));
return;
}
for (int num = s; num <= n + 1 - (k - rowSize); ++num) {
// 选择当前数字
row[rowSize] = num;
dfs(ans, row, rowSize + 1, num + 1, n, k);
}
}
}
c
/**
*
*
* @param ans 最终结果
* @param returnSize 结果行数量
* @param row 行记录
* @param rowSize 行数字数量
* @param s 开始数字
* @param n
* @param k
*/
void dfs(int **ans, int *returnSize, int *row, int rowSize, int s, int n, int k)
{
if (rowSize == k)
{
int *tmp = malloc(sizeof(int) * k);
for (int i = 0; i < k; i++)
{
tmp[i] = row[i];
}
ans[(*returnSize)++] = tmp;
return;
}
for (int num = s; num <= n + 1 - (k - rowSize); ++num) {
// 选择当前数字
row[rowSize] = num;
dfs(ans, returnSize, row, rowSize + 1, num + 1, n, k);
}
}
int a(int n, int m)
{
int c = 1;
while (m > 0)
{
c *= n--;
m--;
}
return c;
}
/**
* 计算返回数量
*
* @param n
* @param k
* @return int
*/
int calcReturnSize(int n, int k)
{
k = fmin(k, n - k);
return a(n, k) / a(k, k);
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int **combine(int n, int k, int *returnSize, int **returnColumnSizes)
{
int **ans = malloc(calcReturnSize(n, k) * sizeof(int *));
int row[k];
*returnSize = 0;
dfs(ans, returnSize, row, 0, 1, n, k);
*returnColumnSizes = malloc(*returnSize * sizeof(int));
for (int i = 0; i < (*returnSize); ++i)
{
(*returnColumnSizes)[i] = k;
}
return ans;
}
c++
class Solution {
private:
/**
*
* @param ans 最终结果
* @param row 行记录
* @param s 开始数字
* @param n
* @param k
*/
void dfs(vector<vector<int>> &ans, vector<int> &row, int s, int n, int k)
{
if (row.size() == k)
{
ans.push_back(row);
return;
}
for (int num = s; num <= n + 1 - (k - row.size()); ++num)
{
// 选择当前数字
row.push_back(num);
dfs(ans, row, num + 1, n, k);
row.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k)
{
vector<vector<int>> ans;
vector<int> row;
dfs(ans, row, 1, n, k);
return ans;
}
};
python
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(s):
if len(row) == k:
ans.append(row[:])
return
for num in range(s, n + 2 - (k - len(row))):
# 选择当前数字
row.append(num)
dfs(num+1)
row.pop()
ans = []
row = []
dfs(1)
return ans
go
func combine(n int, k int) (ans [][]int) {
var dfs func([]int, int, int)
dfs = func(row []int, rowSize int, s int) {
if rowSize == k {
ans = append(ans, append([]int{}, row...))
return
}
for num := s; num <= n+1-(k-rowSize); num++ {
// 选择当前数字
row[rowSize] = num
dfs(row, rowSize+1, num+1)
}
}
dfs(make([]int, k), 0, 1)
return
}
rust
impl Solution {
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
fn dfs(ans: &mut Vec<Vec<i32>>, row: &mut Vec<i32>, rowSize: i32, s: i32, n: i32, k: i32) {
if rowSize == k {
ans.push(row.to_vec());
return;
}
(s..n + 2 - (k - rowSize)).for_each(|num| {
// 选择当前数字
row[rowSize as usize] = num;
dfs(ans, row, rowSize + 1, num + 1, n, k);
});
}
let mut ans = Vec::new();
dfs(&mut ans, &mut vec![0; k as usize], 0, 1, n, k);
ans
}
}
javascript
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const dfs = (row, rowSize, s) => {
if (rowSize === k) {
ans.push([...row]);
return;
}
for (let num = s; num <= n + 1 - (k - rowSize); ++num) {
// 选择当前数字
row[rowSize] = num;
dfs(row, rowSize + 1, num + 1);
}
}
const ans = [];
dfs([], 0, 1);
return ans;
};
typescript
function combine(n: number, k: number): number[][] {
function dfs(row: number[], rowSize : number, s: number) {
if (rowSize === k) {
ans.push([...row]);
return;
}
for (let num = s; num <= n + 1 - (k - rowSize); ++num) {
// 选择当前数字
row[rowSize] = num;
dfs(row, rowSize + 1, num + 1);
}
}
const ans = [];
dfs([], 0, 1);
return ans;
};
原题传送门：https://leetcode-cn.com/problems/uUsW3B/
原题传送门：https://leetcode-cn.com/problems/combinations/
非常感谢你阅读本文~
欢迎【????点赞】【⭐收藏】【????评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
最后
以上就是热心铅笔为你收集整理的【算法leetcode每日一练】剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合：样例 1：样例 2：提示：分析题解原题传送门：https://leetcode-cn.com/problems/uUsW3B/原题传送门：https://leetcode-cn.com/problems/combinations/的全部内容，希望文章能够帮你解决【算法leetcode每日一练】剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合剑指 Offer II 080. 含有 k 个元素的组合 | 77. 组合：样例 1：样例 2：提示：分析题解原题传送门：https://leetcode-cn.com/problems/uUsW3B/原题传送门：https://leetcode-cn.com/problems/combinations/所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复