-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-78-Subsets.java
76 lines (62 loc) · 2.57 KB
/
LeetCode-78-Subsets.java
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length == 0) return result;
java.util.Arrays.sort(nums); // not necessary
List<Integer> set = new ArrayList<Integer>();
int start = 0;
subset(nums, result, set, start);
return result;
}
private void subset(int[] nums, List<List<Integer>> result, List<Integer> set, int start){
result.add(new ArrayList<Integer>(set));
for(int i = start; i < nums.length; i++){
// if(set.contains(nums[i])){ // don't need, because it's distinct array
// continue;
// }
set.add(nums[i]);
subset(nums, result, set, i + 1);
set.remove(set.size() - 1);
}
}
}
/*
1.Recursive
If the order doesn't matter and no duplicate, then don't need sort. For the combination sum, we may need sort.
2.Iterative.
Appending each value in nums to the existing lists in the result.
*/
class Solution {
// 1. Recursive
// public List<List<Integer>> subsets(int[] nums) {
// List<List<Integer>> result = new ArrayList<List<Integer>>();
// if (nums == null) return result;
// List<Integer> list = new ArrayList<>();
// subsets(nums, 0, result, list);
// return result;
// }
// private void subsets(int[] nums, int start, List<List<Integer>> result, List<Integer> list) {
// result.add(new ArrayList<>(list));
// for (int i = start; i < nums.length; i++) {
// list.add(nums[i]);
// subsets(nums, i + 1, result, list);
// list.remove(list.size() - 1);
// }
// }
// 2.Iterative
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
result.add(new ArrayList<>());
for (int i : nums) {
List<List<Integer>> temp = new ArrayList<List<Integer>>();
for (List<Integer> sub : result) {
List<Integer> list = new ArrayList<>(sub); // have to create a copy of the sub list, otherwise the next line will pollute the existing result.
list.add(i);
temp.add(list);
}
result.addAll(temp); // we have to add the temp after we finished the above for-loop, as it's loop the result.
}
return result;
}
}