> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/backtrack/78.-subsets.md).

# 78. Subsets

[Given an integer array `nums`, return *all possible subsets (the power set)*.](https://leetcode.com/problems/subsets/)

```java
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);
        }
    }   
}
```