78. Subsets (not use befroe, so int I = start, dfs(i+1)

recusion tree is: use or not use

subset: 元素 unique, 不使用重複數字

subset, 不允許使用重複數字

with int i = start, dfs(i+1) to next level, 下層挑選的數字必定是沒用過, 所以不會有重複

time: O(2^n) or O(2^n*n) , the subset's count is 2^n

space: O(2^n) or O(2^n*n)

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

why n*2^n?

this n is from where? this res.add(new ArrayList<>(list)); -> totally needs O(n)

new Array(list) is a copy op...

this total is n