Difference Between Subarrays, Subsequences and Subsets.

In this post, we are going to understand the basic difference between Subarrays, Subsequences, and Subsets with respect to the Array data structure. These three terms are often used in coding problems and confused many of us which makes the question more difficult to understand. Let's discuss each term one by one with examples:

Subarrays: 

A subarray is a contiguous part of the main array in which the elements of the subarray are together and next to each other in relative order. If the given array has n number of elements then there can be n*(n + 1)/2 number of non-empty subarrays possible.

Example of Subarrays:

Given arr[ ] = {3, 5, 7, 2}
Total number of elements n = 4
The number of subarrays possible = n*(n+1)/2 = 4*(4+1)/2 = 4*5/2 = 10

List of all possible subarrays:
[3]
[5]
[7]
[2]
[3, 5]
[5, 7]
[7, 2]
[3, 5, 7]
[5, 7, 2]
[3, 5, 7, 2]

Subsequences:

Given arr[ ] = {3, 5, 7, 2}
Total number of elements n = 4
The number of subsequences possible = 2^n - 1 = 2^4 - 1 = 15

List of all possible subsequences:
[3]
[5]
[7]
[2]
[3, 5]
[3, 7]
[3, 2]

[5, 7]

[5, 2]

[7, 2]
[3, 5, 7]

[3, 5, 2]

[3, 7, 2]

[5, 7, 2]

[3, 5, 7, 2]

Subsets:

Given A[] = {2, 3, 5} and B[] = {1, 2, 3, 4, 5, 6}

A ⊆ B as all the elements of A is present in B