250+ TOP MCQs on Subset Sum Problem and Answers

Data Structures & Algorithms Multiple Choice Questions 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

Answer: b
Clarification: 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.

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

Answer: b
Clarification: 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)

Answer: a
Clarification: 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(n²)
d) O(sum*n)

Answer: d
Clarification: 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

Answer: a
Clarification: 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.

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
Clarification: 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)
Answer: d
Clarification: 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; 

d)

if(sum
Answer: b
Clarification: 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  
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

Answer: c
Clarification: 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?







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

Answer: b
Clarification: 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  
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
Clarification: 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).
 complete set of 1000+