The following paradigm can be used to find the solution of the problem in…
2018
The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with sum equal to K:
- A.
Divide and Conquer
- B.
Dynamic Programming
- C.
Greedy Algorithm
- D.
Branch and Bound
Attempted by 132 students.
Show answer & explanation
Correct answer: B
This problem describes the classic Subset Sum Problem. While a brute-force approach checks all subsets with exponential time complexity O(2^n), Dynamic Programming is the standard paradigm for solving this efficiently. It utilizes a table to store intermediate results of subproblems, achieving pseudo-polynomial time complexity O(n*K), where n is the number of elements and K is the target sum.