Count Subsets with Sum K
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Count Subsets with Sum K, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Subsequences, Subset Sum, Time Complexity, Space Complexity, Arrays, dynamic programming, memoization, combinatorics, tabulation, space optimization, recursion, time complexity analysis.
Count Subsets with Sum K Problem Statement Given an array ARR with N positive integers and an integer K, you need to find the number of subsets of ARR whose elements sum up to K. Note: If there are duplicate numbers in the array, they should be treated as distinct elements based on their indices. For example, if ARR = [1, 2, 2] and K = 3, then {1, 2 first occurrence} and {1, 2 second occurrence} are considered two distinct subsets. Input Specification The first line contains two integers, N and K, representing the number of elements in the array and the target sum, respectively. The second line contains N positive integers, ARR[0], ARR[1], ..., ARR[N 1], representing the elements of the array. Output Specification Print a single integer, which is the total number of subsets whose sum is equal to K. Constraints 1 <= N <= 1000 0 <= K <= 1000 1 <= ARR[i] <= 1000 Sample Test Cases Sample Input 1: Sample Output 1: Explanation: Given ARR = [1, 2, 2, 3] and K = 3. The subsets that sum to 3 are: 1. {1, 2} (using ARR[0] and ARR[1]) 2. {1, 2} (using ARR[0] and ARR[2]) 3. {3} (using ARR[3]) Thus, there are 3 such subsets.