78. Subsets

# Medium

Subset problems are generally solved by RECURSIVE.

Build subsets from NULL, add one element whose positioin is after current element each time.

Recursive process for array [1, 2, 3]

Java

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<Integer> level = new ArrayList<Integer>();
        helper(nums, 0, level);
        return res;
    }
    
    public void helper(int[] nums, int i, ArrayList<Integer> level) {
        res.add(new ArrayList(level));  // copy level to res
        if(i == nums.length) return;
        
        for(int j = i; j < nums.length; j ++) {
            level.add(nums[j]);
            helper(nums, j + 1, level);
            level.remove(level.size() - 1);
        }
    }
}

Python

1. In Python, list.append(sublist) in helper function gets wrong output(list = [[], [], [], [], []]), should be list.append(sublist[:]).

2. After each sub.append, must remove that element just added in helper function.

Time complexity = $O(n*2^n)$ , $n$ is to copy the subset to result.

Space complexity = $O(n*2^n)$