[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));

revisited dec 2025

also be careful. i made mistake of passign idx+1 instead of i+1 to dfs parameter. thats wrong. we need to carry forward the current pointer (i) and not idx cuz if its idx, its value is not incremented and fixed. So we will add the same number in that index that we already added in tmp list.

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)