> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/78.-subsets.md).
# 78. Subsets (not use befroe, so int I = start, dfs(i+1)
## recusion tree is: use or not use
subset: 元素 unique, 不使用重複數字
subset, 不允許使用重複數字
with int i = start, dfs(i+1) to next level, 下層挑選的數字必定是沒用過, 所以不會有重複
time: O(2^n) or O(2^n\*n) , the subset's count is 2^n
space: O(2^n) or O(2^n\*n)
```java
class Solution {
public List> subsets(int[] nums) {
List> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
helper(res, new ArrayList<>(), nums, 0);
return res;
}
// backtracking, [], [1], [2], [3], index +1 [1,2]...
private void helper(List> res, List list, int[] nums, int index) {
res.add(new ArrayList<>(list));
for (int i = index; i< nums.length; i++) {
list.add(nums[i]);
helper(res, list, nums, i + 1);
list.remove(list.size() - 1);
}
}
}
```
why n\*2^n?
this n is from where?\
this res.add(new ArrayList<>(list)); -> totally needs O(n)
new Array(list) is a copy op...
this total is n
