要求:给定一个含不同整数的集合,返回其所有的子集
注意事项:子集中的元素排列必须是非降序的,解集必须不包含重复的子集。
样例
如果 S = [1,2,3]
,有如下的解:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
思路:不考虑非降序,一个个数字插进去,每一层插进去一个,每一个都有两种情况,加进去和不加进去。就是遍历数组里面所有的元素,每次取出第一个list,往里面加入,或者不加入,就有了两种情况的list产生,再把这两种list加进去,依次循环。
这样的做法是降序的,不符合题意,但是在此处还是贴一下代码。
public class Solution { /* * @param nums: A set of numbers * @return: A list of lists */ public List<List> subsets(int[] nums) { // write your code here ArrayList<List> res=new ArrayList<List>(); ArrayListlist=new ArrayList(); if(nums==null ||nums.length == 0){ return res; } res.add(list); for(int i=0;i<nums.length;i++){ for(int j=0;j<Math.pow(2,i);j++){ Listtemp=res.get(0); res.remove(0); ArrayListtemp2=new ArrayList(temp); temp2.add(temp2.size(),nums[i]); res.add(temp2); res.add(temp); } } return res; } }
我们看到上面代码的错误样例如下:
输入
[4,1,0]
输出
[[],[0],[1],[1,0],[4],[4,0],[4,1],[4,1,0]]
期望答案
[[],[0],[0,1],[0,1,4],[0,4],[1],[1,4],[4]]
为什么会这样子呢,其实非降序这个要求只是一个幌子,我们只要在加入之前对数组进行排序就可以通过啦。
代码如下:
public class Solution { /* * @param nums: A set of numbers * @return: A list of lists */ public List<List> subsets(int[] nums) { // write your code here ArrayList<List> res=new ArrayList<List>(); ArrayListlist=new ArrayList(); if(nums==null ){ return res; } res.add(list); Arrays.sort(nums); for(int i=0;i<nums.length;i++){ for(int j=0;j<Math.pow(2,i);j++){//每一层的个数都是2的n次方 Listtemp=res.get(0); res.remove(0);//把第一个取出来 ArrayListtemp2=new ArrayList(temp); temp2.add(temp2.size(),nums[i]); res.add(temp2);//加入一个数,放进去 res.add(temp);//不加数,放进去 } } return res; } }