一、题目
1、算法题目
“给定两个整数nk，返回范围[1,n]中所有可能的k个数的组合。”
题目链接：
来源：力扣（LeetCode）
链接：77. 组合 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定两个整数 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、思路分析
这道题是求所有的组合，也就是一个问题找出所有的方法，这时候就可以使用回溯算法。
回溯算法是深度优先遍历算法，对于组合问题，排列问题而言，不计较一个组合内元素的顺序性
因此需要按某种顺序展开搜索，才能不遗漏。
2、代码实现
代码参考：
public class Solution { public IList<IList<int>> Combine(int n, int k) { var res = new List<IList<int>>(); recruion(1, n, k, new int[k], res); return res; } void recruion(int start, int n, int k, int[] item, IList<IList<int>>res) { if(k == 0){ res.Add(item.ToList()); return; } for(var i=start;i<=n-k+1;i++){ item[item.Length - k] = i; recruion(i+1, n, k-1, item, res); } } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
可以使用深度优先算法解决此问题。利用数组来存储每个符合条件的结果。
因为结果的个数都是k，所以计算下一个结果时不需要清空原有结果数据，否则就变成了回溯算法了。
