-
Notifications
You must be signed in to change notification settings - Fork 25
Expand file tree
/
Copy pathCombine.java
More file actions
35 lines (29 loc) · 841 Bytes
/
Combine.java
File metadata and controls
35 lines (29 loc) · 841 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package com.lga.algorithm.tag.homework.Week_03;
import java.util.LinkedList;
import java.util.List;
/**
* 77. 组合
* https://leetcode-cn.com/problems/combinations/
*/
public class Combine {
private List<List<Integer>> ans = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
LinkedList<Integer> trace = new LinkedList<>();
backtrace(0, n, k, trace);
return ans;
}
private void backtrace(int i, int n, int k, LinkedList<Integer> trace) {
//终止条件
if (trace.size() == k) {
ans.add(new LinkedList<>(trace));
return;
}
while (i++ < n) {
trace.add(i);
//进入下一层
backtrace(i, n, k, trace);
//返回上一层
trace.removeLast();
}
}
}