Problem Description
Given a set of distinct integers A, return all possible subsets.
NOTE:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
- Also, the subsets should be sorted in ascending ( lexicographic ) order.
- The list is not necessarily sorted.
Solution
For each element, we can two choices - either to include that element or exclude it from the current subset.
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
public class Solution {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
public ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> A) {
//We can sort the list since the problem needs the elements in sorted order in each subset
Collections.sort(A);
//main helper method that will generate all subsets and add to answer list
helper(A, new ArrayList<>(), 0);
//The subsets themselves need to be sorted for which we will need to use a comparator
Collections.sort(ans, new Comparator<ArrayList<Integer>>(){
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
//Loop through each element in first list and check if any of the element is smaller/larger
for(int i=0; i<o1.size() && i<o2.size(); i++){
if(o1.get(i) > o2.get(i)) return 1;
if(o1.get(i) < o2.get(i)) return -1;
}
//If all elements in list1 are same as list2, we need to compare their size
if(o1.size() > o2.size()) return 1;
else return -1;
}
});
return ans;
}
public void helper(ArrayList<Integer> list, ArrayList<Integer> current, int i){
//When i is equal to size of the list, we must have taken a decision whether to include or exclude each of the elements
//At this point, we can add the subset we have generated
if(i == list.size()){
//Note that we cannot simply do: ans.add(current)
//The reference would be the same, so the same list would get modified
ans.add(new ArrayList<>(current));
return;
}
//Including the current element
current.add(list.get(i));
helper(list, current, i+1);
//Excluding the current element
//We need to remove from current list because we had added it in the previous step
current.remove(current.size()-1);
helper(list, current, i+1);
}
}
ANOTHER APPROACH (Not optimized)
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
77
78
79
80
81
82
public class Solution {
public int[][] subsets(int[] A) {
int n = A.length;
//total number of subsets will be 2^n
int totalSubsets = (1<<n);
//sort the array so that we form subsets which are already sorted (individual subsets will be sorted only)
Arrays.sort(A);
//answer list
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
//basically we take taking numbers from [0, 2^n]
//each one will have a different bit set/unset and they will also form different subsets
//if kth bit is set in the current number, then include A[k] in the current subset
//Example: i = 0101 => current subset will be: {A[0], A[2]} because the 0th and 2nd bit are set.
for(int i=0; i<totalSubsets; i++){
ArrayList<Integer> subset = new ArrayList<>();
for(int pos=0; pos<n ; pos++){
if(checkSetBit(pos, i)){
subset.add(A[pos]);
}
}
list.add(subset);
}
//sort the complete arraylist
list = sortList(list);
return convertListTo2DArray(list);
}
public ArrayList<ArrayList<Integer>> sortList(ArrayList<ArrayList<Integer>> list) {
Collections.sort(list, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
int n1 = o1.size(), n2 = o2.size();
for (int i = 0; i < Math.min(n1, n2); i++) {
int cmp = o1.get(i).compareTo(o2.get(i));
if (cmp != 0) {
return cmp;
}
}
return Integer.compare(n1, n2);
}
});
return list;
}
public boolean checkSetBit(int pos, int n){
if( ((1<<pos)&n) != 0)
return true;
else
return false;
}
public static int[][] convertListTo2DArray(ArrayList<ArrayList<Integer>> list) {
int[][] arr = new int[list.size()][];
for (int i = 0; i < list.size(); i++) {
ArrayList<Integer> sublist = list.get(i);
arr[i] = new int[sublist.size()];
for (int j = 0; j < sublist.size(); j++) {
arr[i][j] = sublist.get(j);
}
}
return arr;
}
}