# 78. Subsets (not use befroe, so int I = start, dfs(i+1)

## recusion tree is: use or not use

<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fqr7ImqHoW3ViLcvXi7E9%2Fimage.png?alt=media&#x26;token=f9a418ac-56d2-450a-b142-f18d9dee508b" alt=""><figcaption></figcaption></figure>



![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MdRNdRkBszm975YLVeA%2F-MdRVNJCRS0zDztBhDUr%2Fimage.png?alt=media\&token=bf0e45c8-dc21-4328-8555-5012c081035b)

subset: 元素 unique, 不使用重複數字

subset, 不允許使用重複數字

with int i = start, dfs(i+1) to next level, 下層挑選的數字必定是沒用過, 所以不會有重複

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FLRt2oZG4kecXi8dI0sU5%2Fimage.png?alt=media\&token=04761647-8227-4524-a78a-d25968ac78ac)



time: O(2^n) or O(2^n\*n) , the subset's count is 2^n &#x20;

space: O(2^n) or O(2^n\*n)

```java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> 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<List<Integer>> res, List<Integer> 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...\


<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FPKLe0ubNXmQ4BnH50pIf%2Fimage.png?alt=media&#x26;token=034bc1f5-62c4-4a2f-afeb-b021ffbeb2a2" alt=""><figcaption></figcaption></figure>

this total is n

<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F8DNbYODKYzYzPbmZP5DC%2Fimage.png?alt=media&#x26;token=09ebad5a-5afa-429c-84e2-7105985c97f7" alt=""><figcaption></figcaption></figure>
