“给定两个整数nk,返回范围[1,n]中所有可能的k个数的组合。”
题目链接:
来源:力扣(LeetCode)
链接:77. 组合 - 力扣(LeetCode) (leetcode-cn.com)
给定两个整数 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]]
这道题是求所有的组合,也就是一个问题找出所有的方法,这时候就可以使用回溯算法。
回溯算法是深度优先遍历算法,对于组合问题,排列问题而言,不计较一个组合内元素的顺序性
因此需要按某种顺序展开搜索,才能不遗漏。
代码参考:
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);
}
}
}
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
可以使用深度优先算法解决此问题。利用数组来存储每个符合条件的结果。
因为结果的个数都是k,所以计算下一个结果时不需要清空原有结果数据,否则就变成了回溯算法了。