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

# 02/16/2022 78

78\. Subsets

Method 1:

While iterating through all numbers, for each new number, we can either pick it or not pick it 1, if pick, just add current number to every existing subset. 2, if not pick, just leave all existing subsets as they are. We just combine both into our result.

Time O(n \* 2^n) we loop through each number in the `nums` array once, which is O(n). For each number we go through, we double the size of result, thus the next for loop will take twice as long, hence O(2^n)

Space O(n \* 2^n)

```
   class Solution { 
       public List<List> subsets(int[] nums) { 
           List<List> result = new ArrayList<>(); if(nums == null || nums.length == 0) return result; 
           //empty set result.add(new ArrayList<>()); 
            
            for(int n: nums){
                int size = result.size();
                for(int i = 0; i < size; i++){
                    List<Integer> subset = new ArrayList<>(result.get(i));
                    //pick the element;
                    subset.add(n);
                    //comnine into result
                    result.add(subset);
                }
            }
            return result;
}
```

}

Method 2:

use backtracking. The difference between this problem with other combination problems is the base condition. Whenever you get a path, you should add it to the result list.

Time O(n \* 2^n)

Space O(n)  We are using O(N) space to maintain path, and are modifying path in-place with backtracking.

```
```

```
   class Solution { 
      List<List> result = new ArrayList<>(); 
      LinkedList path = new LinkedList<>(); 
      public List<List> subsets(int[] nums) { 
      if(nums == null || nums.length == 0) 
         return result; 
         backtracking(nums, 0); return result; }
   
       
        private void backtracking(int[] nums, int startIndex){
          result.add(new ArrayList<>(path));
       //can ignore
       if(startIndex >= nums.length) return;
       for(int i = startIndex; i < nums.length; i++ ){
           path.add(nums[i]);
           //cannot contain duplicate elements
           backtracking(nums, i + 1);
           path.removeLast();
       }
   }
```

}