Subsets - Leetcode Solution

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:

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.

1