首页 > 代码库 > LeetCode: Combinations 解题报告
LeetCode: Combinations 解题报告
Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
SLOUTION 1:
一段时间不写真心容易不记得。
这是一道典型的模板题。以下是模板写法。
1. 必须时刻注意，for循环里 是i+1不是Index+1，这个老是会忘记。我们当前取过后，应该是处理下一个位置。
2. start 应该是从1开始。这个是这题的特别情况，一般idnex是0开始。
3. combination的题目，注意因为没有顺序，所以为了避免重复的一些解，我们只考虑递增的解。下一个排列题就不一样了。
1 // 注意，因为求的是组合，所以我们要考虑一下顺序问题，只需要考虑升序。这样的话就不会有重复的 2 // 的组合。 3 public void dfs(int n, int k, List<Integer> path, List<List<Integer>> ret, int start) { 4 if (path.size() == k) { 5 ret.add(new ArrayList<Integer>(path)); 6 return; 7 } 8 9 // 注意这里的条件i <= n 取n也是合法的！10 // Example: 11 for (int i = start; i <= n; i++) {12 path.add(i);13 14 // 注意，最后一个参数是i + 1，不是start + 1！！15 dfs(n, k, path, ret, i + 1);16 path.remove(path.size() - 1);17 }18 }
SLOUTION 2:
为了优化，在for 中加了一个判断，及时终止。i <= (n - k + 1)
1 // 注意，因为求的是组合，所以我们要考虑一下顺序问题，只需要考虑升序。这样的话就不会有重复的 2 // 的组合。 3 public void dfs2(int n, int k, List<Integer> path, List<List<Integer>> ret, int start) { 4 if (0 == k) { 5 ret.add(new ArrayList<Integer>(path)); 6 return; 7 } 8 9 // 注意这里的条件i <= n 取n也是合法的！10 // Example: 11 for (int i = start; i <= (n - k + 1); i++) {12 path.add(i);13 14 // 注意，最后一个参数是i + 1，不是start + 1！！15 dfs(n, k - 1, path, ret, i + 1);16 path.remove(path.size() - 1);17 }18 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/combination/Combine_1203.java
LeetCode: Combinations 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。