Subsets Solution

In this page, we will solve the Subsets problem using three different approaches: brute force, hash table, and two-pointer technique. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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.

Examples

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

Constraints

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

---

Solution for Subsets Problem

Intuition and Approach

The Subsets problem asks us to generate all possible subsets of a given set of unique integers. This involves considering every possible combination of elements, including the empty set and the set itself. The total number of subsets for a set with 𝑛 elements is $2^n$.

• Brute Force
• Bit Manipulation
• Backtracking

Approach 1: Brute Force (Naive)

The brute force approach to solve the Subsets problem involves generating all possible combinations of the elements in the input array. This can be done by iterating through every possible subset size, from 0 to the size of the array, and using combinations to generate the subsets of each size.

Implementation

Live Editor

function SubsetsGenerator() {
  const nums = [1, 2, 3];
  
  const generateSubsets = (nums) => {
    const result = [[]];
    for (let i = 0; i < nums.length; i++) {
      const len = result.length;
      for (let j = 0; j < len; j++) {
        result.push([...result[j], nums[i]]);
      }
    }
    return result;
  };

  const result = generateSubsets(nums);

  return (
    <div>
      <p>
        <b>Input:</b> nums = [{nums.join(", ")}]
      </p>
      <p>
        <b>Output:</b> [
        {result.map((subset, index) => (
          <span key={index}>
            [{subset.join(", ")}]
            {index < result.length - 1 ? ', ' : ''}
          </span>
        ))}
        ]
      </p>
    </div>
  );
}

Result

Loading...

Codes in Different Languages

JavaScript

Written by @ajay-dhangar

  var subsets = function(nums) {
 let result = [[]];
 for (let i = 0; i < nums.length; i++) {
     const len = result.length;
     for (let j = 0; j < len; j++) {
         result.push([...result[j], nums[i]]);
     }
 }
 return result;
};

TypeScript

Written by @ajay-dhangar

 function subsets(nums: number[]): number[][] {
 let result: number[][] = [[]];
 for (let i = 0; i < nums.length; i++) {
     const len = result.length;
     for (let j = 0; j < len; j++) {
         result.push([...result[j], nums[i]]);
     }
 }
 return result;
}

Python

Written by @ajay-dhangar

 class Solution:
def subsets(nums):
 result = [[]]
 for num in nums:
     for subset in result[:]:
         result.append(subset + [num])
 return result

Java

Written by @ajay-dhangar

 class Solution {
 public List<List<Integer>> subsets(int[] nums) {
     List<List<Integer>> result = new ArrayList<>();
     result.add(new ArrayList<>());
     for (int num : nums) {
         int size = result.size();
         for (int i = 0; i < size; i++) {
             List<Integer> subset = new ArrayList<>(result.get(i));
             subset.add(num);
             result.add(subset);
         }
     }
     return result;
 }
}

C++

Written by @ajay-dhangar

class Solution {
public:
 vector<vector<int>> subsets(vector<int>& nums) {
     vector<vector<int>> result = {{}};
     for (int num : nums) {
         int size = result.size();
         for (int i = 0; i < size; i++) {
             vector<int> subset = result[i];
             subset.push_back(num);
             result.push_back(subset);
         }
     }
     return result;
 }
};

Complexity Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$
• Where n is the length of the input array nums.
• The time complexity is $O(n^2)$ because we are iterating through the array twice.
• The space complexity is $O(1)$ because we are not using any extra space.
• This approach is not efficient and is not recommended for large inputs.

Note

Which is the best approach? and why?

In general, for small to medium-sized input sets (say, up to 30 or 40 elements), bit manipulation can be more efficient and concise. However, for larger input sets or when you have additional constraints or filtering conditions, backtracking may be a better choice due to its memory efficiency and flexibility. Ultimately, the decision between bit manipulation and backtracking depends on the specific requirements of your problem, the size of the input set, and any additional constraints or conditions that need to be considered.

References

• LeetCode Problem: Subsets Problem
• Solution Link: Subsets Solution on LeetCode
• Authors LeetCode Profile: Ajay Dhangar