# Solution For Subsets

Problem Statement:

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

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

Solution:

Approach:

The approach to solve the problem is to use backtracking. The idea is to generate all possible subsets by making a decision on each element of the given set (whether to include the element in a particular subset or not). The backtracking algorithm will exhaustively search through all possible combinations of the given set and store the valid subsets.

Algorithm:

1) Initialize a list to store the subsets.
2) Define the backtracking function:
a) If the current subset is valid (i.e., contains only distinct elements), append the subset to the subsets list.
b) Loop through the remaining elements of the input set:
i) Add the current element to the current subset.
ii) Recursively call the backtracking function with the updated subset and remaining input set.
iii) Remove the current element from the current subset to backtrack.
3) Call the backtracking function with an empty current subset and the entire input set.
4) Return the subset list.

Python Code:

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

``````    def backtrack(curr, remainder):
if len(curr) == len(set(curr)): # check if the current subset is valid
res.append(curr)
for i in range(len(remainder)):
backtrack(curr + [remainder[i]], remainder[i+1:])

backtrack([], nums)
return res
``````

“`

Time Complexity:
The time complexity of the solution is O(2^n), where n is the length of the input set. This is the worst-case scenario when all elements of the input set are included in each possible subset.

Space Complexity:
The space complexity of the solution is also O(2^n) due to the same reason.

## Step by Step Implementation For Subsets

```class Solution {
public List> subsets(int[] nums) {
List> result = new ArrayList<>();
List curr = new ArrayList<>();
backtrack(result, curr, nums, 0);
return result;
}

private void backtrack(List> result, List curr, int[] nums, int start) {
for (int i = start; i < nums.length; i++) {
backtrack(result, curr, nums, i + 1);
curr.remove(curr.size() - 1);
}
}
}```
```class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# create an empty list to store all the subsets
subsets = []

# create an empty subset and add it to the list of subsets
subsets.append([])

# for every element in the input list
for elem in nums:
# for every subset in the list of subsets
for i in range(len(subsets)):
# create a new subset by adding the current element to the subset at index i
new_subset = list(subsets[i])
new_subset.append(elem)
# add the new subset to the list of subsets
subsets.append(new_subset)

# return the list of subsets
return subsets```
```var subsets = function(nums) {
var result = [[]];

for (var i = 0; i < nums.length; i++) {
for (var j = 0, len = result.length; j < len; j++) {
result.push(result[j].concat(nums[i]));
}
}

return result;
};```
```class Solution {
public:
vector> subsets(vector& nums) {
vector> res;
vector cur;
subsets(nums, 0, cur, res);
return res;
}

void subsets(vector& nums, int start, vector& cur, vector>& res) {
res.push_back(cur);
for (int i = start; i < nums.size(); ++i) {
cur.push_back(nums[i]);
subsets(nums, i + 1, cur, res);
cur.pop_back();
}
}
};```
```public IList> Subsets(int[] nums)
{
IList> result = new List>();

// sort the array
Array.Sort(nums);

// get all the possible subsets
GetSubsets(nums, 0, new List(), result);

return result;
}

public void GetSubsets(int[] nums, int index, List current, IList> result)
{
// base case - add the current subset to the result
if(index == nums.Length)
{
return;
}

// recursive case 1 - include the current element in the subset