Subset Sum Problem Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Subset Sum Problem”.

1. Under what condition any set A will be a subset of B?
a) if all elements of set B are also present in set A
b) if all elements of set A are also present in set B
c) if A contains more elements than B
d) if B contains more elements than A
View Answer

2. What is a subset sum 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 and printing true or false based on the result
c) finding the sum of elements present in a set
d) finding the sum of all the subsets of a set
View Answer

3. Which of the following is true about the time complexity of the recursive solution of the subset sum 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)
View Answer

4. What is the worst case time complexity of dynamic programming solution of the subset sum problem(sum=given subset sum)?
a) O(n)
b) O(sum)
c) O(n²)
d) O(sum*n)
View Answer

5. Subset sum problem is an example of NP-complete problem.
a) true
b) false
View Answer

6. Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.
a) true
b) false
View Answer

7. Which of the following is not true about subset sum 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

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

if(sum==0)
return true;

b)

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

c)

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

d)

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

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

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

a) 12
b) 4 6 2
c) True
d) False
View Answer

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

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

a) true
b) false
c) 0
d) error in code
View Answer

11. What will be the worst case time complexity for the following code?

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

a) O(n log n)
b) O(n²)
c) O(2ⁿ)
d) O(n² log n)
View Answer

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]