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

Answer: b
Explanation: Any set A will be called a subset of set B if all elements of set A are also present in set B. So in such a case set A will be a part of set B.
advertisement

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

Answer: b
Explanation: In subset sum problem check for the presence of a subset that has sum of elements equal to a given number. If such a subset is present then we print true otherwise false.

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

Answer: a
Explanation: Subset sum 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 worst case.

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(n2)
d) O(sum*n)
View Answer

Answer: d
Explanation Subset sum 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. Subset sum problem is an example of NP-complete problem.
a) true
b) false
View Answer

Answer: a
Explanation: Subset sum problem takes exponential time when we implement a recursive solution. Subset sum problem is known to be a part of NP complete problems.
advertisement

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

Answer: b
Explanation: The recursive solution to subset sum 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 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

Answer: d
Explanation: Recursive solution of subset sum 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 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; 
advertisement

d)

if(sum<0)
   return true;
if (n ==0 && sum!= 0) 
   return false; 
View Answer
Answer: b
Explanation: The base case condition defines the point at which the program should stop recursion. 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.
 
 

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

Answer: c
Explanation: The given code represents the recursive approach of solving the subset sum problem. The output for the code will be true if any subset is found to have sum equal to the desired sum, otherwise false will be printed.

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

advertisement
#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

Answer: b
Explanation: The given code represents the dynamic programming approach of solving the subset sum problem. The output for the code will be true if any subset is found to have sum equal to the desired sum, otherwise false will be printed.

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(n2)
c) O(2n)
d) O(n2 log n)
View Answer

Answer: c
Explanation: The given code represents the recursive approach solution of the subset sum problem. It has an exponential time complexity as it will require to check for all subsets in the worst case. It is equal to O(2n).

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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn