78. Subsets

Given an integer array nums, return all possible subsets (the power set).

class Solution {
    
    // memorize the solution
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, new ArrayList<>(), res, 0);
        return res;        
    }
    // start is used to prevent duplication: 
    // only the numbers behind the start can be added to the list
    private void dfs(int[] nums, List<Integer> subset, List<List<Integer>> res, int start){
        //  add the list come from previous recursion
        res.add(new ArrayList<>(subset));
        
        for (int i = start; i<nums.length; i++){
            subset.add(nums[i]);
            // remember the start = i+1 in next recursion
            dfs(nums, subset, res, i+1);
            subset.remove(subset.size()-1);
        }
    }   
}