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

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # edge case
        result = []
        result.append([])
        if len(nums) == 0:
            return result
        
        # regular case
        sub = []
        self.helper(nums, sub, result, 0)
        return result
    
  # index is the next available element's index      
    def helper(self, nums, sub, result, index):
        # stop condition
        if index == len(nums):
            return        
        
        for i in range(index, len(nums)):
            sub.append(nums[i])
            result.append(sub[:])           
            self.helper(nums, sub, result, i+1)
            sub.pop()

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)$