Sets are a group of elements available for computation. The array is one of the most commonly used types of sets. Array is amongst top used concepts in computer science. And you might have heard this term a lot! 

But do you know that these sets or arrays can be further divided into several parts? The sets can be divided into different parts based on the element placement and order. These parts are – 

  • Subsequence
  • Substring/subset
  • Subarray

Arrays and the further parts of arrays are quite popular amongst interviewers. Various questions based on subsets, subsequences, and subarrays are asked during coding and technical assessment at the tech giants. 

These questions include minimum subset sum difference, print subarray of a given array, reverse the subsets of the array, or longest palindrome subsequence. 

To resolve such questions, you will need to pay a lot of attention to arrays and their parts. 

In this article, we will particularly talk about one of the most important bifurcation of arrays i.e. the subsets. 

If you do not know how the subsets are formed and on what basis you can form these subsets you are at the right place. Let us get you acquainted with this concept. 

To establish a strong foundation of this concept, let’s first understand what are the subsets. 

 

What are subsets?

Subsets can easily be defined as a part of their parent set. The elements in the subsets are placed without any restriction of continuity and order. 

This means that the elements placed next to each other or in a specific order don’t need to form a subset. You can select any number of elements from a set to generate a subset. 

In short, if you create a set of elements belonging to a particular set, a subset will be formed. 

There are two important things about subsets that you must keep in mind:

  • The empty set is always a subset of the parent set
  • The set itself is always considered to be its subset. 

Let’s understand this with an example

Let A be an array or a set of first 5 integers. Now, if you wish to create a set, let’s call it B of the first three positive even integers, it will be a subset of A. 

A={0, 1,2,3,4}

B{0, 2,4}

As you can see, the elements of set B are present in set A irrespective of their placement, we will consider B to be a subset of A. 

Do you know that there is one more important term associated with the subsets that are widely used in interviews? This term is power set! 

A power set is simply a set of all the subsets for the given array  thus, a power set will contain all the subsets of an array in the form of sets only. 

Do you know the power set will contain two types of subsets? 

Let’s discuss the types of subsets and understand their working through detailed examples. 

 

Types of subsets

There are two main categories in which the subsets are further classified. These are proper and improper subsets. Description of both the types of subsets is given below – 

Proper subset

Proper subsets are part of an array in which at least one element of the subset is missing from the parent set. The proper subset is a set of elements available in a parent set given that at least one element is missing from the parent set. 

Let’s understand this with a working example, let’s consider an array of the first five positive integers. The array A will look like {0, 1,2,3,4}. Now, let’s consider another set or array that shows the first 4 non zero numbers. This array will look like {1, 2,3,4}. As you can notice, element 0 is missing from the parent array. In this case, the second array will be considered as a proper subset of the first array or set. 

Let’s consider a detailed example 

Example

Let A be an array of the first 3 digits that are divisible by 7. The array becomes {7, 14,21}

The subsets of this array are as follows:

  • {7}
  • {14}
  • {21}
  • {7, 14,21}
  • {7, 14}
  • {14, 21}
  • And {7, 21}

Can you pick out the proper subsets amongst all these? The proper subsets of this array will be {7, 14}, {14, 21} And {7, 21},{7},{14},{21} and {}.

Do you know you can calculate the number of proper subsets each set will have? Well, the formula of calculating it is quite simple to understand. 

The number of proper subsets of a set is equal to 2n-1. Where n is the number of elements inside the parent set. For example, in the above stated example, the number of elements is 3. Hence, the number of proper subsets becomes 2(to the power of 3)-1 i.e 8-1=7.

This is how you can calculate the proper subsets of a set. 

Improper subset

The improper subset is simply the subset in which the elements are exactly same as the parent set. It indicates that when you form a set of elements that are available in the parent set without missing any element. 

You can understand the improper subsets as the exact opposite or inverse of the proper subsets since the proper and improper subsets form the power set. 

Let’s consider an example of the first 3 digits divisible by 3. The array becomes {3, 6,9}. 

Now, the possible subsets of the above mentioned array will be

  • {3}
  • {6}
  • {9}
  • {3, 6}
  • {3, 9}
  • {9, 6}
  • {3, 6,9}
  • {}

Can you pick out a subset that contains all the elements of the parent set? It will be {3, 6,9}. This is the improper subsets. 

You can also say that improper subsets are simply the sets themselves. It can be calculated as 2n-(2n-1) i.e. 1.

 

Winding up

A popular interview question is an example of improper subsets. It is the longest palindrome subsequence. Whereas, if you try to find out the minimum subset sum difference, you will have to consider proper and improper subsets that must be clear to you by now!