78. Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets. Example
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
题意：求出一个给定数组数的subsets.
回溯法：这个helper是求解包含当前元素的所有子集。 只要扫一遍即可。 代码
class Solution {
public void helper(int[] nums, List<Integer> tmp, List<List<Integer>> ret, int start) {
ret.add(new ArrayList<>(tmp));
for(int i = start; i < nums.length; i++) {
tmp.add(nums[i]);
helper(nums, tmp, ret, i + 1);
tmp.remove(tmp.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
helper(nums, new ArrayList<>(), ret, 0);
return ret;
}
}
Bitmask法： 代码
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
int n = nums.length;
for(int i = 0; i < (1 << n); i++) {
List<Integer> tmp = new ArrayList<>();
int pos = 0;
for (int j = i; j > 0; j >>= 1) {
if((j & 1) == 1) tmp.add(nums[pos]);
pos++;
}
ret.add(new ArrayList<>(tmp));
}
return ret;
}
}