/
Solution.java
69 lines (60 loc) · 2.08 KB
/
Solution.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
/**
* Time : O(2^n); Space: O()
* @tag : Array; Backtracking; Bit Manipulation
* @by : Steven Cooks
* @date: Jun 7, 2015
*************************************************************************
* Description:
*
* My Submissions Question Solution
* Given a set of distinct integers, nums, return all possible subsets.
*
* Note: Elements in a subset must be in non-descending order.
* The solution set must not contain duplicate subsets.
* For example, If nums = [1,2,3], a solution is:
* [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
*
*************************************************************************
* {@link https://leetcode.com/problems/subsets/ }
*/
package _078_Subsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/** see test {@link _078_Subsets.SolutionTest } */
public class Solution {
// try to insert each number into all existing subsets
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
// push initial empty subset
res.add(new ArrayList<>());
for (int num : nums) {
int sz = res.size(); // we don't need temp list any more
for (int i = 0; i < sz; i++) {
List<Integer> list = new ArrayList<>(res.get(i));
list.add(num);
res.add(list);
}
}
return res;
}
// we have to use temporary list
public List<List<Integer>> subsets2(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
// push initial empty subset
res.add(new ArrayList<>());
for (int num : nums) {
// try insert num into all existing subsets
List<List<Integer>> temp = new ArrayList<>();
for (List<Integer> sub : res) {
List<Integer> list = new ArrayList<>(sub);
list.add(num);
temp.add(list);
}
res.addAll(temp);
}
return res;
}
}