[LC] 77. Combinations
2024-08-31 22:57:14
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
] Time: O(C(N, k))
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
start = 0
my_list = []
self.dfs(n, k, 1, my_list, res)
return res def dfs(self, n, k, start, my_list, res):
if k == 0:
res.append(list(my_list))
return
for i in range(start, n + 1):
my_list.append(i)
# need to use i + 1 instead of start + 1 for the next level
self.dfs(n, k - 1, i + 1, my_list, res)
my_list.pop()
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
helper(res, new ArrayList<Integer>(), n, k, 1);
return res;
} private void helper(List<List<Integer>> res, List<Integer> list, int n, int k, int start) {
if (k == 0) {
res.add(new ArrayList<>(list));
return;
}
// need to go deeper based on current i and ignore the previous result, so that use i + 1
for (int i = start; i <= n; i++) {
list.add(i);
helper(res, list, n, k - 1, i + 1);
list.remove(list.size() - 1);
}
}
}
最新文章
- 承接unity外包:2016年VR产业八大发展趋势
- [IOS多线程]的使用:防止进行HTTP数据请求时,UI卡死。
- iOS开发Swift篇—(七)函数(1)
- ASP.NET MVC进阶二
- qbxt十一系列一
- java.lang.OutOfMemoryError: unable to create new native thread如何解决
- [Hibernate]dynamic-insert和dynamic-update属性
- weblogic启动报错之未修改hosts产生错误
- [转] 使用CodeViz生成C/C++函数调用关系图
- 经典Loading 动漫赏析
- 【转】python之random模块分析(一)
- Android逆向分析(2) APK的打包与安装
- vs变量监视提示-VAR-CREATE: UNABLE TO CREATE VARIABLE OBJECT解决方法
- input标签(文本域和文件域)
- MatCap冰冻效果Shader
- JS正则表达式方法
- 理解本真的REST架构风格(转,解释的最清楚)
- Guava Cache 使用笔记
- 丑数(LintCode)
- Shiro理解与总结