In this coding problem, we need to find the power-set of given input without duplicates.

Introduction

In this article, we discuss the subsets of a given input. This is one of the most popular questions asked in coding interviews.

Companies that have asked this in their coding interview are Apple, Microsoft, Amazon, Facebook, and many more.

Problem Statement

We need to write a program that finds all possible subsets ( the power set) of a given input. The solution set must not contain duplicate subsets.

Example 01:

Input:[1,2,3]Output:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 02:

Input:[100]Output:[[],[100]]

Explanation: The subsets of any given input are equal to its power set.

if, inputn = 3, then, powerset =>2^n ​​=2^3 =8.

Assume input has a length greater than or equal to1.

Hint: Use the left-shift operator to achieve this.

Thought Process

In this program, we find the power set of a given input using bitwise operations.

In general, if we haven elements then the subsets are2^​n subsets.

So for every possible case of having at least two elements, we can see that an element is present and not present in the subsets.

Think of a solution that is iterative, uses bitwise operators, and generates the powerset.

Here is how we generate each subset using the outer-loop variablecounter. Here is a table indicating how the value gets generated based on thecounter input.

Algorithm

We need to consider acounter variable that starts from0 to2^​n​​ - 1.

For every value, we are considering the binary representation and here we use the set bits in the binary representation to generate corresponding subsets.

1. If all set bits are0, then the corresponding subset is empty[].

2. If the last bit is1, then we put1 in the subset as[1].

Steps:

We use two loops here, the outer-loop starts from0 to2^​n​​ - 1, and the inner loop continues to input array lengthn.

In the inner loop, we conditionally check(counter & (1 << j)) != 0), if yes, then we print the corresponding element from an array.

Solution

constSubsets=nums=>{constresult=[];letn=nums.length;letpowSize=Math.pow(2,n);for(leti=0;i<powSize;i++){constval=[];for(letj=0;j<n;j++){if((i&(1<<j))!==0){val.push(nums[j]);}}result.push('['+val+']');}returnresult;}console.log('Result:'+Subsets([1,2,3]));

Complexity Analysis

Time Complexity:O(n*2^n), time complexity isn times the powerset.

*Space Complexity: *O(2^n), We are storing2^​n​​ subset elements in an array. So the extra space is directly proportional toO(2^n​​).

Extras

If you are interested in mastering bit tricks, I've got a course that are loved by more than 100k+ programmers.

In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. The course has simple explanation with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators.

These bit-tricks could help in competitive programming and coding interviews in running algorithms mostly inO(1) time.

This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies.

To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll move on to learn about the six different bitwise operators: AND, OR, NOT, XOR, and bit shifting. Throughout, you will get tons of hands-on experience working through practice problems to help sharpen your understanding.

By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency!! 🤩

Link to my course:Master Bit Manipulation for Coding Interviews.