-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution_216.java
More file actions
47 lines (41 loc) · 1.14 KB
/
Solution_216.java
File metadata and controls
47 lines (41 loc) · 1.14 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
package com.hilbert25.leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* @author : hilbert25
* @version 创建时间：2017年3月10日 下午8:53:30 LeetCode com.hilbert25.leetcode
* Solution_216
*/
public class Solution_216 {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public static List<List<Integer>> combinationSum3(int k, int n) {
List<Integer> list = new ArrayList<Integer>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (n < k * (k - 1) / 2)
return result;
result = search(k, n, 1, 0, list, result);
return result;
}
public static List<List<Integer>> search(int k, int n, int cur, int sum, List<Integer> list,
List<List<Integer>> result) {
if (k == 0)
return result;
for (int i = cur; i <= 9; i++) {
if (sum + i < n) {
sum += i;
list.add(i);
result = search(k - 1, n, i + 1, sum, list, result);
list.remove(list.size() - 1);
sum -= i;
} else if (sum + i == n && k == 1) {
list.add(i);
result.add(new ArrayList<Integer>(list));
list.remove(list.size() - 1);
} else
break;
}
return result;
}
}