# Subsets Or Powerset

In subsets or powerset problem, 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 elements.

## Introduction

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

## Problem statement

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

### Example 1

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

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

### Example 2

``````Input: [100]

Output: [[], [100]]``````

## Explanation

The subsets of any given input are equal to its power set. If input `n = 3`, then powerset => `2n` ​​= `23` = `8`. We assume that the input has a length greater than or equal to `1`.

Hint: We can use the left-shift operator to achieve this.

## Thought process

This program finds the power set of a given input using bitwise operations.

In general, if we have `n` elements, then the subsets are `2​n`. Therefore, for every possible case of having at least two elements, we can see that an element is present and not present in the subsets.

Let’s think of an iterative solution that uses bitwise operators and generates the powerset.

Here is how we generate each subset using the outer-loop variable `counter`. The following table indicates how the value is generated based on the `counter` input.

### Table representation

Counter (in decimal) Counter (in binary) Subset
0 000 []
1 001 [1]
2 010 [2]
3 011 [1, 2]
4 100 [3]
5 101 [1, 3]
6 110 [2, 3]
7 111 [1, 2, 3]

### Algorithm

We need to consider a `counter` variable that starts from`0` to `2​n​​ - 1`.We consider the binary representation for every value and use the set bits in the binary representation to generate the corresponding subsets.

1. If all set bits are `0`, the corresponding subset is empty `[]`.
2. If the last bit is `1`, we put `1` in the subset as `[1]`.

### Steps

We use two loops here. The outer loop starts from `0` to `2``​n``​​ - 1`, and the inner loop continues to input the array length `n`.

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

## Solutions

### Java

``````import java.util.*;

class Subsets {
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
int powSize = (int) Math.pow(2, n);

for (int i = 0; i < powSize; i++) {
List<Integer> val = new ArrayList<>();
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
}
}
}

return result;
}

public static void main(String[] args) {
int[] nums = {1, 2, 3};
System.out.println(subsets(nums));
}
}``````

### Python

``````def subsets(nums):
result = []

n = len(nums)
pow_size = 2 ** n

for i in range(pow_size):
val = []
for j in range(n):
if (i & (1 << j)) != 0:
val.append(nums[j])
result.append(val)

return result

print('Result:', subsets([1, 2, 3]))
``````

### JavaScript

``````const Subsets = nums => {
const result = [];

let n = nums.length;
let powSize = Math.pow(2, n);

for (let i = 0; i < powSize; i++) {
const val = [];
for (let j = 0; j < n; j++) {
if ((i & (1 << j)) !== 0) {
val.push(nums[j]);
}
}
result.push('[' + val + ']');
}
return result;
}

console.log('Result: ' + Subsets([1, 2, 3]));``````

### C++

``````#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

void subsets(vector<int>& nums){
int n = nums.size();
int powSize = pow(2, n);

for(int counter = 0; counter < powSize; counter++){
for(int j = 0; j < n; j++){
if((counter & (1 << j)) != 0){
cout<<"[" <<nums[j] << "]";
}
}
cout<<endl;
}
}

int main() {
vector<int> array = { 1, 2, 3 };
subsets(array);
}``````

### TypeScript

``````const Subsets = (nums: number[]): number[][] => {
const result: number[][] = [];

let n: number = nums.length;
let powSize: number = Math.pow(2, n);

for (let i: number = 0; i < powSize; i++) {
const val: number[] = [];
for (let j: number = 0; j < n; j++) {
if ((i & (1 << j)) !== 0) {
val.push(nums[j]);
}
}
result.push(val);
}
return result;
}

console.log('Result:', Subsets([1, 2, 3]));``````

## Complexity Analysis

### Time complexity

Time complexity is O(n*2n), where `n` times the powerset.

### Space complexity

We are storing 2n subset elements in an array. So the extra space is directly proportional to O(2n).

Coding Interview QuestionsData Structures and AlgorithmsArraysBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!