This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses 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

View Answer

Explanation: 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

d) finding subsets with equal sum of elements

View Answer

Explanation: 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)

View Answer

Explanation: 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(n^{2})

d) O(sum*n)

View Answer

Explanation: 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

View Answer

Explanation: 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

View Answer

Explanation: 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

Explanation: 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<0) return true; if (n ==0 && sum!= 0) return false;View Answer

Explanation: 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 <stdio.h> #include <stdbool.h> 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

View Answer

Explanation: 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 <stdio.h> 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

View Answer

Explanation: 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(n^{2})

c) O(2^{n})

d) O(sum*n)

View Answer

Explanation: 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).

**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__.