【leetcode】子集

【leetcode】子集

题目：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

思路：

从题目中可以看出，当你求子集[1,2,3]的时候用到了子集[1,2],而求子集[1,2]又用到了子集[1]。所以我们可以发现，我们所求的每一个子集都用到了上一个子集，因此我们可以用递归算法来求。

首先求单个子集，比如[1]，然后作为参数进行递归得到第二个子集[1,2]，然后一步步递归，得到所有子集。

注意要包括空集。

java代码：

class Solution {
   public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
       res.add(new ArrayList<>());
        if(nums ==null || nums.length ==0) {
            return res;
        }
 
        subsets(res, nums, new ArrayList<>(), 0);
 
        return res;
    }
 
    private void subsets(List<List<Integer>> res, int[] nums, ArrayList<Integer> list, int k) {
        for(int i=k;i<nums.length;i++) {
           list.add(nums[i]);
            res.add(new ArrayList<>(list));
            subsets(res, nums, list, i+1);
            list.remove(list.size()-1);
        }
    }
}