Check if Subsequence Exists with Sum K
Subsequences Pattern DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Check if there exists a subsequence with sum K, Recursion, Backtracking, Subsequences, Time Complexity, Space Complexity, Arrays, space complexity, dynamic programming, backtracking, recursion, time complexity analysis, DP on Subsequences / Subsets.
Check if there exists a subsequence with sum K Given an array arr of N integers and an integer K, determine if there exists a subsequence of arr whose elements sum up to K. Input: The first line contains a single integer N (1 <= N <= 20), the number of elements in the array. The second line contains N space separated integers arr[0], arr[1], ..., arr[N 1] ( 10^9 <= arr[i] <= 10^9). The third line contains a single integer K ( 10^14 <= K <= 10^14), the target sum. Output: Print "YES" if there exists a subsequence whose elements sum up to K, otherwise print "NO". Examples: Input 1: Output 1: Explanation 1: The subsequence [1, 2] sums to 3. The subsequence [3] also sums to 3. Input 2: Output 2: Explanation 2: No subsequence of [1, 2, 3] sums to 7.