Count All Subsequences with Sum K
Subsequences Pattern DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Count all subsequences with sum K, Recursion, Backtracking, Dynamic Programming, Subsequences, Arrays, Time Complexity, Space Complexity, Optimization, combinatorics, recursion, dynamic programming, backtracking.
Count Subsequences with Sum K Problem Statement Given an array of integers arr and a target sum K, your task is to find and return the total number of non empty subsequences of arr whose elements sum up exactly to K. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. 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 space separated integers, representing the elements of the array arr. Output Specification Output a single integer representing the count of subsequences with a sum equal to K. Constraints 1 <= N <= 20 0 <= arr[i] <= 1000 0 <= K <= N 1000 Sample Test Case Input Output Explanation For the array [1, 2, 3] and target sum K = 3, the subsequences that sum up to 3 are: [1, 2] (1 + 2 = 3) [3] (3 = 3) Therefore, the total count is 2.