[Leetcode] 78. Subsets

https://leetcode.com/problems/subsets/description/

initial

typical backtracking but in java
we cannot do
ans.add(my_temp_list)

this adds just the reference to the temp list, not the actual list. Instead wat we should do is

ans.add(new ArrayList<>(so_far));

sol

class Solution {
    public List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        ans.add(new ArrayList<>());
        List<Integer> temp = new ArrayList<>();
        dfs(0,nums,temp);
        return ans;
    }

    public void dfs(int index, int[] nums, List<Integer> so_far){
        if (index>=nums.length){
            return;
        } 
        for(int i=index;i<nums.length;i++){
            so_far.add(nums[i]);
            ans.add(new ArrayList<>(so_far));
            dfs(i+1,nums,so_far);
            so_far.remove(so_far.size()-1);
        }
    }
}

complexity

for n elements, there can be 2^n number of subsets
and when we add our tmp list to ans list, it takes o(n)

so time is n* 2^n
space is recursion dfs depth of o(n)