78.给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
1
2 3
3
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
//走过的所有路径都是子集的一部分,所以都要加入到集合中
list.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
//做出选择
tempList.add(nums[i]);
//递归,i+1 防止重复结果
backtrack(list, tempList, nums, i + 1);
//撤销选择
tempList.remove(tempList.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
// 子集个数
int resCount = 1<<len;
// i 其实就是每种子集对应的二进制数的十进制
for(int i=0;i<resCount;i++){
List<Integer> list = new ArrayList<>();
// 看是否包含 nums 中某个数
for(int j=0;j<len;j++){
// 如果包含就添加到 list
if((i>>j&1)==1)list.add(nums[j]);
}
res.add(list);
}
return res;
}
[]->[[],1]->[[],1,2,12]->[[],1,2,12,3,13,23,123]
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
for(int num : nums){
int size = res.size();
for(int j=0;j<size;j++){
List<Integer> tempList = new ArrayList<>(res.get(j));
tempList.add(num);
res.add(tempList);
}
}
return res;
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
dfs(nums,res,0);
return res;
}
public void dfs(int[] nums,List<List<Integer>> res,int index){
if(index >= nums.length)return;
for(int i=0,j=res.size();i<j;i++){
List<Integer> list = new ArrayList(res.get(i));
list.add(nums[index]);
res.add(list);
}
dfs(nums,res,index+1);
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), nums, 0);
return res;
}
public void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, int index){
if(index == nums.length){
res.add(new ArrayList<>(list));
return;
}
// 不选,直接继续递归
dfs(res, list, nums, index + 1);
// 选择(加入 list)
list.add(nums[index]);
// 选完再递归
dfs(res, list, nums, index + 1);
// 撤销选择
list.remove(list.size() - 1);
}