250+ TOP MCQs on Set Partition Problem and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Set Partition Problem”.

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) an empty set

Answer: b
Clarification: Power set of a set is defined as the set of all subsets. Ex- if there is a set S={1,3} then power set of set S will be P={{},{1},{3}{1,3}}.

2. What is the set partition problem?
a) finding a subset of a set that has sum of elements equal to a given number
b) checking for the presence of a subset that has sum of elements equal to a given number
c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result
d) finding subsets with equal sum of elements

Answer: c
Clarification: In set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such subsets are present then we print true otherwise false.

3. Which of the following is true about the time complexity of the recursive solution of set partition problem?
a) It has an exponential time complexity
b) It has a linear time complexity
c) It has a logarithmic time complexity
d) it has a time complexity of O(n2)
Answer: a
Clarification: Set partition problem has both recursive as well as dynamic programming solution. The recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case.

4. What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a) O(n)
b) O(sum)
c) O(n2)
d) O(sum*n)

Answer: d
Clarification: Set partition problem has both recursive as well as dynamic programming solution. The dynamic programming solution has a time complexity of O(n*sum) as it as a nested loop with limits from 1 to n and 1 to sum respectively.

5. Set partition problem is an example of NP complete problem.
a) true
b) false

Answer: a
Clarification: Set partition problem takes exponential time when we implement a recursive solution. Set partition problem is known to be a part of NP complete problems.

6. Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.
a) true
b) false

Answer: b
Clarification: The recursive solution to set partition problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. So dynamic programming solution is faster in terms of time complexity.

7. Which of the following is not true about set partition problem?
a) the recursive solution has a time complexity of O(2n)
b) there is no known solution that takes polynomial time
c) the recursive solution is slower than dynamic programming solution
d) the dynamic programming solution has a time complexity of O(n log n)
View Answer

Answer: d
Clarification: Recursive solution of set partition problem is slower than dynamic problem solution in terms of time complexity. Dynamic programming solution has a time complexity of O(n*sum).

8. Which of the following should be the base case for the recursive solution of a set partition problem?
a)

If(sum%2!=0)
   return false;
if(sum==0)
   return true;

b) 

If(sum%2!=0)
   return false;
if(sum==0)
   return true;
if (n ==0 && sum!= 0) 
   return false;

c) 

if (n ==0 && sum!= 0) 
    return false;

d) 

if(sum
Answer: b
Clarification: In this case, we need to make sure that, the sum does not become 0 and there should be elements left in our array for recursion to happen. Also if the sum of elements of the set is an odd number then that set cannot be partitioned into two subsets with an equal sum so under such a condition false should be returned. 

 
 

9. What will be the output for the given code?




#include  
#include  
bool func1(int arr[], int n, int sum) 
{ 
    if (sum == 0) 
	return true; 
    if (n == 0 && sum != 0) 
	return false; 
    if (arr[n-1] > sum) 
	return func1(arr, n-1, sum); 
    return func1(arr, n-1, sum) || func1(arr, n-1, sum-arr[n-1]); 
} 
bool func (int arr[], int n) 
{ 	
	int sum = 0; 
	for (int i = 0; i < n; i++) 
	sum += arr[i]; 	
	if (sum%2 != 0) 
	return false; 
	return func1 (arr, n, sum/2); 
} 
int main() 
{ 
    int arr[] = {4,6, 12, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    if (func(arr, n) == true) 
	printf("true"); 
    else
	printf("false"); 
    return 0; 
}
















a) true
b) false
c) 4 6 2
d) 12


Answer: a
Clarification: The given code represents the recursive approach of solving the set partition problem. The code checks whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such a partition is possible then we print true otherwise false. In this case true should be printed. 


10. What will be the output for the given code?
















#include 
bool func (int arr[], int n) 
{ 
	int sum = 0; 
	int i, j; 
	for (i = 0; i < n; i++) 
	sum += arr[i];
	if (sum%2 != 0) 
	return false; 
	bool partition[sum/2+1][n+1]; 
	for (i = 0; i <= n; i++) 
	partition[0][i] = true; 
	for (i = 1; i <= sum/2; i++) 
	partition[i][0] = false;	 
	for (i = 1; i <= sum/2; i++) 
	{ 
	    for (j = 1; j <= n; j++) 
	    { 
		partition[i][j] = partition[i][j-1]; 
		if (i >= arr[j-1]) 
		partition[i][j] = partition[i][j] || partition[i - arr[j-1]][j-1]; 
	    }		 
	}	 
	return partition[sum/2][n]; 
}	
int main() 
{ 
    int arr[] = {3, 3, 4, 4, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    if (func(arr, n) == true) 
	printf("true"); 
    else
	printf("false"); 
    return 0; 
}
















a) true
b) false
c) 0
d) error


Answer: b
Clarification: The given code represents the dynamic programming approach of solving set partition problem. The code checks whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such a partition is possible then we print true otherwise false. In this case, false should be printed. 


11. What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a) O(n log n)
b) O(n2)
c) O(2n)
d) O(sum*n)


Answer: d
Clarification: The auxiliary space complexity of set partition problem is required in order to store the partition table. It takes up a space of n*sum, so its auxiliary space requirement becomes O(n*sum).


 & Algorithms.


 and Answers.

Leave a Reply

Your email address will not be published. Required fields are marked *