# Description

https://leetcode.com/problems/subsets/

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

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

```Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

Example 2:

```Input: nums = [0]
Output: [[],[0]]
```

Constraints:

• `1 <= nums.length <= 10`
• `-10 <= nums[i] <= 10`
• All the numbers of `nums` are unique.

## Explanation

The problem is a typical backtracking coding problem. We can have a recursion helper function to add visited subsets to the final results. Remember to make a deep copy when we are adding a subset to the results.

## Java Solution

``````class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> results = new ArrayList<>();

if (nums == null || nums.length == 0) {
return results;
}

Arrays.sort(nums);

List<Integer> subset = new ArrayList<>();
toFindAllSubsets(nums, results, subset, 0);

return results;
}

private void toFindAllSubsets(int[] nums, List<List<Integer>> results, List<Integer> subset, int startIndex) {

for (int i = startIndex; i < nums.length; i++) {
toFindAllSubsets(nums, results, subset, i + 1);
subset.remove(subset.size() - 1);
}
}
}``````

## Python Solution

``````class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
results = []

self.helper(results, nums, [], 0)

return results

def helper(self, results, nums, subset, start):
results.append(list(subset))

for i in range(start, len(nums)):
num = nums[i]
subset.append(num)
self.helper(results, nums, subset, i + 1)
subset.pop()
``````
• Time complexity: O(N * 2^N) to generate all subsets and then copy them into the output list. The number for ecursive calls T(n) satisfies the recurrence T(n) = T(n-1) + T(n-2) + T(1) + T(0), which solves to T(n) = O(2^n) .Since we spend O(n) time within a call , the time complexity is O(N * 2^N).
• Space complexity: O(N * 2^N) to keep all the subsets of length N, since each of N elements could be present or absent.

## 4 Thoughts to “LeetCode 78. Subsets”

1. mouli says:

you can try this in binary format

2. anushka kasera says:

cannot understand the the remove bit .