Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
Solution
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
int n = nums.length;
for (int i = (int) Math.pow(2, n); i < (int) Math.pow(2, n + 1); i++) {
// generate bitmasks from 00.000 to 111..111
String bitmask = Integer.toBinaryString(i).substring(1);
List<Integer> curr = new ArrayList<>();
for (int j = 0; j < n; j++) {
if (bitmask.charAt(j) == '1') curr.add(nums[j]);
}
subsets.add(curr);
}
return subsets;
}
public List<List<Integer>> subsets3(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> current = new ArrayList<>();
dfs(0, nums, current, subsets);
return subsets;
}
void dfs(int index, int[] nums, List<Integer> current, List<List<Integer>> subsets) {
if (index == nums.length) {
subsets.add(new ArrayList<>(current));
return;
}
current.add(nums[index]);
dfs(index + 1, nums, current, subsets);
current.remove(current.size() - 1);
dfs(index + 1, nums, current, subsets);
}
public List<List<Integer>> subsets2(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> current = new ArrayList<>();
generateSubsets(0, nums, current, subsets);
return subsets;
}
void generateSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> subsets) {
subsets.add(new ArrayList<>(current));
for (int i = index; i < nums.length; i++) {
current.add(nums[i]);
generateSubsets(i + 1, nums, current, subsets);
current.remove(current.size() - 1);
}
}
}
Solution 2021-11-22
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> curr = new ArrayList<>();
dfs(0, nums, res, curr);
return res;
}
void dfs(int index, int[] nums, List<List<Integer>> res, List<Integer> curr) {
if (index == nums.length) {
res.add(List.copyOf(curr));
return;
}
curr.add(nums[index]);
dfs(index + 1, nums, res, curr);
curr.remove(curr.size() - 1);
dfs(index + 1, nums, res, curr);
}
}