Algorithms and data manipulation are areas where it is important to grasp the ideas behind subarrays, subsequences as well as subsets. This article introduces the concepts of subarrays, subsequences along with subsets in Python. You will find out what these terms actually mean and how they differ from one another in Python. Such an ability will help you solve many coding problems that involve arrays, sequences, as well as set manipulations.

What is Subarray?

An array is a collection of values stored in a continuous block of memory. A subarray is a portion of that array, also stored continuously. In other words, a subarray is any consecutive part of the original array.

Example:

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

Input: arr = [2, 5, 7, 6]
Output: [[2], [2, 5], [2,5,7], [2,5,7,6], [5], [5, 7], [5,7,6], [7], [7, 6], [6]]

Approach:

Iterating over all possible starting and ending indices of subarrays within the given array. For each combination of start and end indices, extracts the corresponding subarray from the original array and adds it to a result list.

Here’s a step-by-step breakdown of the approach:

• Initialize variables, n: Length of the input array, result: An empty list to store the subarrays.
• Use a for loop to iterate over all indices i from 0 to n-1. This loop determines the starting point of each subarray.
  • For each start index i, use another for loop to iterate over all indices j from i+1 to n. This loop determines the ending point of each subarray, ensuring that the subarray starts at i and ends at j.
    • Use array slicing arr[i:j] to extract the subarray from the original array.
    • Append the extracted subarray to the result list.
• After iterating over all possible start and end indices, return the result list containing all the subarrays of the input array.

Below is the implementation of the above approach:

# Finding subarrays of an array
def subarrays(arr):

    n = len(arr)
    result = []

    # Iterate over the start index of the subarray
    for i in range(n):
      
        # Iterate over the end index of the subarray,
        # starting from the start index
        for j in range(i+1, n+1):
          
            # Extract the subarray from the original array
            # and append it to the result list
            result.append(arr[i:j])

    return result


# Example usage
arr = [1, 2, 3]
print("Subarrays of", arr, ":", subarrays(arr))

Subarrays of [1, 2, 3] : [[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

What is Subsequence ?

A subsequence is different from a subarray. While a subarray is a contiguous portion of an array, a subsequence is a sequence of elements from the array that may or may not be consecutive. In other words, a subsequence can be formed by selecting certain elements from the array, in the same order as they appear in the original array, but the selected elements don’t have to be next to each other.

Example:

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

Input: arr = [2,4,5,1]
Output: [] [2] [4] [5] [1] [2,4] [2,5] [2,1] [4,5] [4,1] [5,1] [2,4,5] [2,4,1] [2,5,1] [4,5,1] [2,4,5,1]

Approach:

The idea is to building up the set of subsequences incrementally. It starts with an empty subsequence and then iteratively adds each element of the input array to all existing subsequences.

Here’s a step-by-step breakdown of the approach:

• Create a list result and initialize it with an empty list []. This represents the empty subsequence, which is always a subsequence of any array.
• Use a for loop to iterate over each element arr[i] in the input array.
  • Inside the loop, use a list comprehension to generate new subsequences by adding the current element arr[i] to each existing subsequence in result.
  • The expression [sub + [arr[i]] for sub in result] iterates over the current result list and creates a new subsequence by appending arr[i] to each existing subsequence sub.
  • The resulting list of new subsequences is then added to the result list using the += operator.
• After iterating over all elements, the result list contains all possible subsequences of the input array. Return this list.

Below is the implementation of the above approach:

# Finding subsequences of an array
def subsequences(arr):

    n = len(arr)
    result = [[]]  # Initialize result with an empty subsequence

    # Iterate over each element in the array
    for i in range(n):
      
        # Create new subsequences by adding the current element
        # to all existing subsequences
        result += [sub + [arr[i]] for sub in result]

    return result


# Example usage
arr = [1, 2, 3]
print("Subsequences of", arr, ":", subsequences(arr))

Subsequences of [1, 2, 3] : [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

What is Subset ?

A subset is a collection of elements that are part of a larger set or array. Unlike a subarray, which must be a contiguous sequence of elements from the original array, a subset can contain any combination of elements from the original array, in any order.

Example:

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

Input: arr = [2,4,5,1]
Output: [] [2] [4] [5] [1] [2,4] [2,5] [2,1] [4,5] [4,1] [5,1] [2,4,5] [2,4,1] [2,5,1] [4,5,1] [2,4,5,1]

Approach:

The idea is to building up the set of subsets incrementally. It starts with the empty set and then iteratively adds each element of the input set to all existing subsets.

Here’s a step-by-step breakdown of the approach:

• Create a list result and initialize it with an empty list []. This represents the empty set, which is always a subset of any set.
• Use a for loop to iterate over each element elem in the input set.
• Inside the loop, use a list comprehension to generate new subsets by adding the current element elem to each existing subset in result.
  • The expression [sub + [elem] for sub in result] iterates over the current result list and creates a new subset by appending elem to each existing subset sub.
  • The resulting list of new subsets is then added to the result list using the += operator.
• After iterating over all elements, the result list contains all possible subsets of the input set. Return this list.

Below is the implementation of the above approach:

# Finding subsets of a set
def subsets(arr):

    result = [[]]  # Initialize result with the empty set
    for elem in arr:
      
        # Generate new subsets by adding the current
        # element to all existing subsets
        result += [sub + [elem] for sub in result]
    return result


# Example usage
arr = [1, 2, 3]
print("Subsets of", arr, ":", subsets(arr))

Subsets of [1, 2, 3] : [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Difference Between Subarray, Subsequence and Subsets: