Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums =
If nums =
[1,2,3], a solution is:[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
//DFS, time:O(n^2), space:O(1)
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;
}
subsetsHelper(nums, ans, new ArrayList<Integer>(), 0);
return ans;
}
public void subsetsHelper(int[] nums, List<List<Integer>> ans, List<Integer> list, int start) {
ans.add(new ArrayList<Integer>(list));
for (int i = start; i < nums.length; i++) {
list.add(nums[i]);
subsetsHelper(nums, ans, list, i + 1);
list.remove(list.size() - 1);
}
}
}
/*
bfs:
First, adding an empty list to the ans, then iterate the input array, each time adding the number to all the existed subsets. The new subsets and the previous subsets together make up the new ans.
time:O(n^2), space:O(1)
*/
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;
}
List<Integer> list = new ArrayList<>();
ans.add(list);
for (int i = 0; i < nums.length; i++) {
int size = ans.size();
for (int j = 0; j < size; j++) {
list = new ArrayList<>(ans.get(j));
list.add(nums[i]);
ans.add(list);
}
}
return ans;
}
}
