Generating Subsets Questions and Answers

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Generating Subsets”.

1. What is meant by the power set of a set?
a) subset of all sets
b) set of all subsets
c) set of particular subsets
d) empty set
View Answer

Answer: b
Explanation: Power set of a set is defined as the set of all subsets. Ex- S={1,2} then P={{},{1},{2}{1,2}}.

2. Number of elements in the power set of set S={1,2,3} will be?
a) 2
b) 4
c) 6
d) 8
View Answer

Answer: d
Explanation: Power set of a set is defined as the set of all subsets. Number of elements in the power set of a set having n elements is given as 2ⁿ. Thus, here number of elements will be 2³=8.

3. Number of elements in the power set of set S={1,2,2} will be?
a) 2
b) 4
c) 6
d) 8
View Answer

Answer: c
Explanation: For finding the number of elements in the power set of the given set we need to remove duplicates. So we will be left with 6 unique elements which will be P={{},{1},{2},{1,2},{2,2},{1,2,2}}.

4. Choose the correct statement for the following code segment?

bool check (int N)
{
    if( N & (1 << i) )
        return true;
    else
        return false;
}

a) function returns true if N is odd
b) function returns true if N is even
c) function returns true if ith bit of N is set
d) function returns false if ith bit of N is set
View Answer

Answer: c
Explanation: As the value of 1 << i is 2ⁱ so the given function checks whether the i^th bit of N is set or not. If it is set then the function returns true.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

5. What will be the output for the following code?

#include <stdio.h> 
#include <math.h> 
void PowerSet(char *set, int set_size) 
{ 
	unsigned int pow_size = pow(2, set_size); 
	int count, j; 	
	for(count = 0; count < pow_size; count++) 
	{ 
	     for(j = 0; j < set_size; j++) 
	     { 
 
		if(count & (1<<j)) 
			printf("%c", set[j]); 
	     } 
	     printf(","); 
	} 
} 
int main() 
{ 
	char strset[] = {'a','b','c'}; 
	PowerSet(strset, 3); 
	return 0; 
}

a) a,b,ab,c,ac,bc,abc,
b) a,b,ab,c,ac,bc,abc
c) ,a,b,ab,c,ac,bc,abc,
d) ,abc,bc,ac,c,ab,b,a,
View Answer

Answer: c
Explanation: The given code prints the elements of power set of the given set strset[]. It uses binary counter of appropriate length in order to print corresponding subsets of the given set.

6. What will be the time complexity of the following code?

#include <stdio.h> 
#include <math.h> 
void PowerSet(char *set, int set_size) 
{ 
	unsigned int pow_size = pow(2, set_size); 
	int count, j; 	
	for(count = 0; count < pow_size; count++) 
	{ 
	     for(j = 0; j < set_size; j++) 
	     { 
 
		if(count & (1<<j)) 
			printf("%c", set[j]); 
	     } 
	     printf(","); 
	} 
} 
int main() 
{ 
	char strset[] = {'a','b','c'}; 
	PowerSet(strset, 3); 
	return 0; 
}

a) O(n 2ⁿ)
b) O(n²)
c) O(n log n)
d) O(2ⁿ) (n is the size of set)
View Answer

Answer: a
Explanation: In the given code we have a nested for loop. In this loop the outer loop runs 2ⁿ times and the inner loop runs n times. So the overall time complexity becomes n2ⁿ.

7. What will be the auxiliary space requirement of the following code?

#include <stdio.h> 
#include <math.h> 
void PowerSet(char *set, int set_size) 
{ 
	unsigned int pow_size = pow(2, set_size); 
	int count, j; 	
	for(count = 0; count < pow_size; count++) 
	{ 
	for(j = 0; j < set_size; j++) 
	{ 		
		if(count & (1<<j)) 
			printf("%c", set[j]); 
	} 
	printf(","); 
	} 
} 
int main() 
{ 
	char strset[] = {'a','b','c'}; 
	PowerSet(strset, 3); 
	return 0; 
}

a) O(n)
b) O(1)
c) O(n log n)
d) O(2ⁿ) (n is the size of set)
View Answer

Answer: b
Explanation: The given code prints the elements of power set of the given set strset[]. As this code does not require any extra space for generating the output so its auxiliary space requirement will be O(1).

8. Which of the following code prints the power set of a given set?
a)

#include<iostream>
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) 
        { 
		cout << curr << endl; 
		return; 
	} 	
	Set(str, index , curr + str[index]); 
	Set(str, index + 1, curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

#include<iostream>
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) 
        { 
		cout << curr << endl; 
		return; 
	} 	
	Set(str, index + 1, curr + str[index]); 
	Set(str, index , curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

#include<iostream>
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) 
        { 
		cout << curr << endl; 
		return; 
	} 	
	Set(str, index + 1, curr + str[index]); 
	Set(str, index + 1, curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

#include<iostream>
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) { 
		cout << curr << endl; 
		return; 
	} 
	Set(str, index , curr+str); 
	Set(str, index + 1, curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

View Answer

Answer: c
Explanation: In the correct version we are taking two cases for each element. In the first case the element is included in the subset and in the second case it is not included. So in this manner, we find all the subsets of the given set.

9. The number of elements in the power set increases when there are duplicates present in the set.
a) True
b) False
View Answer

Answer: b
Explanation: In case when duplicates are present in the set then the number of elements in the power set decreases. It is because we remove subsets with identical elements.

10. What of the following code prints the power set of a given set?
a)

#include <bits/stdc++.h> 
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
 
	if (ind == n) 
		return; 
	cout << curr << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

#include <bits/stdc++.h> 
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (ind == 0) 
		return; 
	cout << curr << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

#include <bits/stdc++.h> 
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (ind == n) 
		return; 
	cout << curr << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() -2); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

#include <bits/stdc++.h> 
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (ind == n) 
		return; 	
	cout << str << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

View Answer

Answer: a
Explanation: In the correct version of the code we are fixing a prefix and generate all corresponding subsets. Then after all subsets with a prefix are generated, we replace last character with one of the remaining character.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

« Prev - Data Structure Questions and Answers – Generating Partitions

» Next - Floyd’s cycle-finding algorithm Multiple Choice Questions and Answers (MCQs)

Related Posts:

Recommended Articles: