78.Subsets_(Medium).md

78. Subsets (Medium)

Date and Time: Jun 21, 2024, 1:53 PM (EST)

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

Question:

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] ]

Walk-through:

For this type of question "permutation type", we can also think about the base case to append and return, if i == len(nums). Then we can pop() the last element from subset and add nums[i+1] into subset[], and we repeat pop() from subset and adding nums[i+1].

This is the print of subset[] for each backtrack() call.

[]
[1]
[1, 2]
[1, 2, 3]
[1, 2]
[1]
[1, 3]
[1]
[]
[2]
[2, 3]
[2]
[]
[3]
[]

This is the illustration of backtracking for this problem. To form all possible subsets, we can use empty set [] to create a subset that can skip an element, like "[1, 3]".

Python Solution:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # Run Backtrack, use ptr i to keep track of current index in nums
        # Base case: if i == len(nums), append curSum to res and return
        # Otherwise, increment i += 1 and add new element into curSum

        # TC: O(2^n), n=len(nums), SC: O(2^n)
        res = []
        def backtr(i, curSum):
            if i == len(nums):
                res.append(curSum.copy())
                return
            curSum.append(nums[i])
            backtr(i+1, curSum)
            curSum.pop()
            backtr(i+1, curSum)
        backtr(0, [])
        return res

Time Complexity: $O(2^n)$ each element we have choice to include it or not, so we have total $2^n$ subsets.
Space Complexity: $O(2^n)$

Java Solution:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();
        backtrack(nums, 0, res, subset);
        return res;
    }

    private void backtrack(int[] nums, int index, List<List<Integer>> res, List<Integer> subset) {
        if (index == nums.length) {
            res.add(new ArrayList<>(subset));
            return;
        }
        subset.add(nums[index]);
        backtrack(nums, index+1, res, subset);
        subset.remove(subset.size()-1);
        backtrack(nums, index+1, res, subset);
    }
}

C++ Solution:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> subset;
        backtrack(nums, 0, res, subset);
        return res;
    }
    void backtrack(vector<int>& nums, int index, vector<vector<int>>& res, vector<int>& subset) {
        if (index == nums.size()) {
            res.push_back(subset);
            return;
        }
        subset.push_back(nums[index]);
        backtrack(nums, index+1, res, subset);
        subset.pop_back();
        backtrack(nums, index+1, res, subset);
    }
};