Problem Solving: Subset of Sets

Learn to create a program that determines whether a set is a subset of another set.

We'll cover the following

In this lesson, we’ll incrementally write a program that determines whether or not a set is a subset of another set.

Subset of sets

Task: Report if AA is a subset of BB, or BB is a subset of AA.

This is how we’ll solve the problem:

  1. Initially, we’ll compare the size of both sets. If the first set’s size is less than or equal to the second set, we will check for the first set as a subset of the second set as a superset, and vice versa.

  2. We’ll write a nested loop which, for each element, ee, in the subset, increments the count if e is contained in the superset.

  3. If the count is equal to the size of the subset, this means we have found the subset.

Let’s look at the animation of A as a subset of B.

Now look at the animation of A is not a subset of B.

Implementing A⊆BA \subseteq B

Let’s write down the code for AA is a subset of BB:

Press + to interact
#include<iostream>
using namespace std;
int main(){
    const int sizeA = 5, sizeB = 4;
    int A[sizeA] = {1, 2, 3, 4, 5};
    int B[sizeB] = {1, 2, 3, 4};
	int count =0;
	if (sizeA <= sizeB)
	{
		for (int ai = 0; ai <= sizeA - 1; ai++)
		{
			for (int bi = 0; bi <= sizeB - 1; bi++)
			{
				if (A[ai] == B[bi])   // A[ai] is in B
				{
					count++;  // remember that A[ai] is present
					break;    // no need to check for this number any further
				}             // The inner loop should be ended
			}
		}
		
		if (count == sizeA)
			cout << "\nA is a subset of B.\n";
		else
			cout << "\nNeither is a subset of other.\n";
	}
	else if (sizeA >= sizeB)
	{
		// Write the code for check B is a subset of A
		
	}
}

In line 2, we will compare the sizes of both sets. If set A is the subset of set B then this condition will be true.

In lines 4–14, we check each element of set A in set B. If an element of set A exists in set B then increment in count by 1 and break the loop. Because once we found that number in another set we don’t need to check further. This break statement will save the iterations.

In line 16, if count is equal to the set sizeA. We can say A is a subset of B.

Implementing B⊆AB \subseteq A

Exercise: Now extend the implementation to handle the case where B⊆AB \subseteq A.

Instruction: Write the code in the playground above.

Quiz on two implementations of searching

Here are the two implementations of searching. Observe carefully and see which one is a better implementation:

Subset of sets

1

Look at the two approaches below for finding whether A⊆BA \subseteq B. Which approach is better to solve that saves execution time?

A)
for (int ai = 0; ai <= sizeA - 1; ai++)
{
	for (int bi = 0; bi <= sizeB - 1; bi++)
	{
		if (A[ai] == B[bi])   
		{
			count++;  
			break;    
		}        
	}
}
if (count == sizeA)
	cout << "\nA is a subset of B.\n";
else
	cout << "\nNeither is a subset of other.\n";
Approach 1
B)
for (int bi = 0; bi <= sizeB - 1; bi++)
{
	for (int ai = 0; ai <= sizeA - 1; ai++)
	{
		if (B[bi] == A[ai])
			count++;
	}
}
if (count == sizeB)
	cout << "\nB is a subset of A.\n";
else
	cout << "\n Neither is a subset of other.\n";
Approach 2
Question 1 of 20 attempted