78 Subsets

Leetcode

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

使用递归。每次传递当前列表和下一个 index 。每次复制当前列表，从 index 开始直到数组最后一个元素，加入列表，再进行递归。

这个时间复杂度是 o(nⁿ) ？

class Solution {
    List<List<Integer>> ret;
    int len;
    public List<List<Integer>> subsets(int[] nums) {
        ret=new LinkedList<>();
        List<Integer> first = new ArrayList<>(0);
        ret.add(first);
        len=nums.length;
        addNext(first, nums, 0);
        return ret;
    }
    
    private void addNext(List<Integer> cur, int[] nums, int next){
        for(int i=next;i<len;++i){
            List<Integer> nextList = new ArrayList(cur.size()+1);
            nextList.addAll(cur);
            nextList.add(nums[i]);
            ret.add(nextList);
            if(i+1<len){
                addNext(nextList, nums, i+1);
            }
        }
    }
}