Skip to main content

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 2n2^n.

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

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;
};

Complexity Analysis

  • Time Complexity: O(n2)O(n^2)
  • Space Complexity: O(1)O(1)
  • Where n is the length of the input array nums.
  • The time complexity is O(n2)O(n^2) because we are iterating through the array twice.
  • The space complexity is O(1)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