Last updated on January 19th, 2025 at 06:03 pm

Here, we see a Subsets LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Backtracking, Bit-Manipulation

Companies

Amazon, Bloomberg, Facebook, Uber

Level of Question

Medium

Subsets LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Subsets. This pattern is commonly used to generate all possible subsets (or power sets) of a given set of numbers. The idea is to explore all combinations of including or excluding each element in the input array.

3. Code Implementation in Different Languages

3.1 Subsets C++

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> cache;
        vector<int> temp;
        subsets(nums, cache, temp, 0);
        return cache;
    }
private:
    void subsets(vector<int>& nums, vector<vector<int>>& cache, vector<int> &temp, int start) {
        if(start == nums.size()) {
            cache.push_back(temp);
            return;
        }
        temp.push_back(nums[start]);
        subsets(nums, cache, temp, start + 1);
        temp.pop_back();
        subsets(nums, cache, temp, start + 1);
        }      
};

3.2 Subsets Java

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

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);        
    }
}
}

3.3 Subsets JavaScript

var subsets = function(nums) {
	let res=[]                    // the final arr, which we will display
	let auxArr = [], i=0             // global vars
    function recur(nums,i,auxArr){
        if(i==nums.length) { res.push(auxArr); return } 
        recur(nums, i+1, [...auxArr, nums[i] ] ) //or, we can use 'aux.concat(nums[i])'
        recur(nums, i+1, auxArr) 
    }  
    recur(nums,i,auxArr) // passing the global variable declared already
    return res    
};

3.4 Subsets Python

class Solution(object):
    def subsets(self, nums):
        res = [[]]
        for n in nums:
            for i in range(len(res)):
                res.append(res[i] + [n])
        return res

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(2n)	O(n * 2n)
Java	O(2n)	O(n * 2n)
JavaScript	O(2n)	O(n * 2n)
Python	O(2n)	O(n * 2n)

• All implementations follow the Subsets coding pattern and have the same time and space complexity.
• The differences lie in the approach (recursion, backtracking, or iteration), but the underlying logic remains consistent.