leetcode 数组求子集(subset)

描述

一个数组，求它的子数组，包括空集.

解法

对数组里的数一个一个的添加进结果集，每添加一个，复制前面所有的list,并将新的元素复制给每一个copy的list，再添加新元素作为单独子集，所有元素遍历完成之后，再添加空集即可.

举例

数组S [1, 2, 3]

{1}

{1,2}

{2}

{1,3}

{1,2,3}

{2,3}

{3}

{}

代码

public ArrayList<ArrayList<Integer>> sub(int[] origin) { ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < origin.length; i++) { ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>(); for (ArrayList<Integer> a : resultList) { temp.add(new ArrayList<Integer>(a)); } for (ArrayList<Integer> a : temp) { a.add(origin[i]); } ArrayList<Integer> single = new ArrayList<Integer>(); single.add(origin[i]); temp.add(single); for (ArrayList<Integer> a : temp) { Collections.sort(a); if (!resultList.contains(a)) { resultList.add(a); } } } resultList.add(new ArrayList<Integer>()); return resultList; }