class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void dfs(int u, int[] nums){
        if(u == nums.length){
            res.add(new ArrayList(path));
            return ;
        }

        dfs(u + 1, nums);

        path.add(nums[u]);
        dfs(u + 1, nums);
        path.remove(path.size() - 1);
    }

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        dfs(0, nums);

        return res;
    }
}