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) {
        result.add(new ArrayList<>(curr));
        for (int i = start; i < nums.length; i++) {
            curr.add(nums[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)
    {
        result.Add(new List(current));
        return;
    }
    
    // recursive case 1 - include the current element in the subset
    current.Add(nums[index]);
    GetSubsets(nums, index + 1, current, result);
    
    // recursive case 2 - do not include the current element in the subset
    current.RemoveAt(current.Count - 1);
    GetSubsets(nums, index + 1, current, result);
}