Question
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],
[]
]
Solution 1 -- BFS
Because it's required that subset must be non-descending order, we can sort input array first. We can write out the solution space tree.
For example, input is [1,2,3]
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
If element of last level is [i, j, .., k], then we could traverse elements from [k + 1, .., last] to add one element to construct complete answers.
BFS can be easily implemented to solve this problem. Time complexity is size of solution space tree, ie, Cn0 + Cn1 + Cn2 + .. + Cnn/2
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
List<List<Integer>> results = new ArrayList<List<Integer>>();
List<List<Integer>> current = new ArrayList<List<Integer>>();
results.add(new ArrayList<Integer>());
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < length; i++) {
map.put(nums[i], i);
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(nums[i]);
current.add(tmp);
results.add(tmp);
}
while (current.size() > 0) {
List<List<Integer>> next = new ArrayList<List<Integer>>();
int l = current.size();
for (int i = 0; i < l; i++) {
List<Integer> currentList = current.get(i);
int ll = currentList.size();
int last = currentList.get(ll - 1);
int index = map.get(last);
for (int j = index + 1; j < length; j++) {
// Note: create a new object
List<Integer> newList = new ArrayList<Integer>(currentList);
newList.add(nums[j]);
next.add(newList);
results.add(newList);
}
}
current = next;
}
return results;
}
}
Solution 2 -- DFS
We can transfer this problem to be list all combinations from number 0 to nums.length
And we can get combinations of each size by DFS. Same time complexity as solution 1.
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
List<List<Integer>> results = new ArrayList<List<Integer>>();
results.add(new ArrayList<Integer>());
for (int i = 1; i <= length; i++) {
dfs(nums, 0, results, new ArrayList<Integer>(), i);
}
return results;
}
private void dfs(int[] nums, int start, List<List<Integer>> results, List<Integer> list, int level) {
if (list.size() == level)
results.add(new ArrayList<Integer>(list));
for (int i = start; i < nums.length; i++) {
list.add(nums[i]);
dfs(nums, i + 1, results, list, level);
list.remove(list.size() - 1);
}
}
}