17. 子集

题目链接：

https://www.lintcode.com/problem/subsets/description

给定一个含不同整数的集合，返回其所有的子集。

Example

样例 1：

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

样例 2：

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

Challenge

你可以同时用递归与非递归的方式解决么？

Notice

子集中的元素排列必须是非降序的，解集必须不包含重复的子集。

Input test data (one parameter per line)How to understand a testcase?

思路：

1、首先对数组排序，保证子集中的元素排序必须是非降序的。

2、遍历数组。 如{1,2,3}，若结果子集res初始时为{{}}，遍历到第0个元素将{1}加入子集，res变成{{},{1}}

     遍历到第1个元素，遍历目前的子集，将第1个元素加入子集，多出的子集：{2},{1,2}，res变成{{},{1},{2},{1,2}}

     遍历到第2个元素，遍历目前的子集，将第2个元素加入子集，多出的子集：{3},{1,3},{2,3},{1,2,3},res变成{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}

代码如下：

public class Solution {     /**      * @param nums: A set of numbers      * @return: A list of lists      */     public List<List<Integer>> subsets(int[] nums) {         // write your code here         List<List<Integer>> res = new ArrayList<>();         res.add(new ArrayList<>());         Arrays.sort(nums);         for(int i=0; i<nums.length; i++) {             int resSize = res.size();             for(int j=0; j<resSize; j++) {                 List<Integer> list = new ArrayList<>(res.get(j));                 list.add(nums[i]);                 res.add(list);             }         }         return res;     } }