北京石景山网站建设/百度搜索引擎seo

题目重述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java AC

回溯法

class Solution {private List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums,0,new ArrayList<>());return result;}void dfs(int[] nums,int index,List<Integer> tmpList){result.add(new ArrayList<>(tmpList));for (int i = index; i < nums.length; i++) {tmpList.add(nums[i]);dfs(nums,i+1,tmpList);tmpList.remove(tmpList.size()-1);}}
}

幂解法

思路

• 例如123，那么就是2的三次幂，即8
• 即000到111二进制，那么如果二进制字符串上有1，就代表是要取的

class Solution {public List<List<Integer>> subsets(int[] nums) {double m = Math.pow(2,nums.length);List<List<Integer>> result = new ArrayList();for(int i=0;i<m;i++){List<Integer> tmpList = new ArrayList<>();String bit = Integer.toBinaryString(i);StringBuilder sb = new StringBuilder();for(int j=0;j<nums.length-bit.length();j++){sb.append("0");}sb.append(bit);for(int j=0;j<sb.toString().length();j++){if(sb.toString().charAt(j)=='1'){tmpList.add(nums[j]);}}result.add(tmpList);  }return result;}
}