Given an array arr[] consisting of N integers and an integer K, the task is to find the length of the longest subsequence with a sum equal to K.
Examples:
Input: arr[] = {-4, -2, -2, -1, 6}, K = 0
Output: 3
Explanation:
The longest subsequence is of length 3 which is {-4, -2, 6} having sum 0.
Input: arr[] = {-3, 0, 1, 1, 2}, K = 1
Output: 5
Explanation: The longest subsequence is of length 5 which is {-3, 0, 1, 1, 2} having sum 1.
Naive Approach: The simplest approach to solve the problem is to generate all the possible subsequences of different lengths and check if their sum is equal to K. Out of all these subsequences with sum K, find the subsequence with the longest length.
Time complexity: O(2N)
Recursive & Backtracking Approach: The basic approach of this problem is to sort the vector and find the sum of all the possible subsequences and pick up the subsequence with the maximum length having the given sum. This can be done using Recursion and Backtracking.
Follow the steps below to solve this problem:
- Sort the given array/vector.
- Initialize a global variable max_length to 0, which stores the maximum length subset.
- For every index i in the array, call the recursion function to find out all the possible subsets with elements in the range [i, N-1] having sum K.
- Every time a subset with sum K is found, check if its size is greater than the current max_length value. If yes, then update the value of max_length.
- After all the possible subset sums are computed, return the max_length.
Below is the implementation of the above approach:
C++
// C++ Program to implement the// above approach#include <bits/stdc++.h>using namespace std;// Initialise maximum possible// length of subsequenceint max_length = 0;// Store elements to compare// max_length with its size// and change the value of// max_length accordinglyvector<int> store;// Store the elements of the// longest subsequencevector<int> ans;// Function to find the length// of longest subsequencevoid find_max_length( vector<int>& arr, int index, int sum, int k){ sum = sum + arr[index]; store.push_back(arr[index]); if (sum == k) { if (max_length < store.size()) { // Update max_length max_length = store.size(); // Store the subsequence // elements ans = store; } } for (int i = index + 1; i < arr.size(); i++) { if (sum + arr[i] <= k) { // Recursively proceed // with obtained sum find_max_length(arr, i, sum, k); // popping elements // from back // of vector store store.pop_back(); } // if sum > 0 then we don't // required thatsubsequence // so return and continue // with earlier elements else return; } return;}int longestSubsequence(vector<int> arr, int n, int k){ // Sort the given array sort(arr.begin(), arr.end()); // Traverse the array for (int i = 0; i < n; i++) { // If max_length is already // greater than or equal // than remaining length if (max_length >= n - i) break; store.clear(); find_max_length(arr, i, 0, k); } return max_length;}// Driver codeint main(){ vector<int> arr{ -3, 0, 1, 1, 2 }; int n = arr.size(); int k = 1; cout << longestSubsequence(arr, n, k); return 0;} |
Java
// Java Program to implement the// above approachimport java.util.*;class GFG{ // Initialise maximum possible// length of subsequencestatic int max_length = 0; // Store elements to compare// max_length with its size// and change the value of// max_length accordinglystatic Vector<Integer> store = new Vector<Integer>(); // Store the elements of the// longest subsequencestatic Vector<Integer> ans = new Vector<Integer>(); // Function to find the length// of longest subsequencestatic void find_max_length( int []arr, int index, int sum, int k){ sum = sum + arr[index]; store.add(arr[index]); if (sum == k) { if (max_length < store.size()) { // Update max_length max_length = store.size(); // Store the subsequence // elements ans = store; } } for (int i = index + 1; i < arr.length; i++) { if (sum + arr[i] <= k) { // Recursively proceed // with obtained sum find_max_length(arr, i, sum, k); // popping elements // from back // of vector store store.remove(store.size() - 1); } // if sum > 0 then we don't // required thatsubsequence // so return and continue // with earlier elements else return; } return;} static int longestSubsequence(int []arr, int n, int k){ // Sort the given array Arrays.sort(arr); // Traverse the array for (int i = 0; i < n; i++) { // If max_length is already // greater than or equal // than remaining length if (max_length >= n - i) break; store.clear(); find_max_length(arr, i, 0, k); } return max_length;} // Driver codepublic static void main(String[] args){ int []arr = { -3, 0, 1, 1, 2 }; int n = arr.length; int k = 1; System.out.print(longestSubsequence(arr, n, k));}}// This code is contributed by Princi Singh |
Python3
# Python3 Program to implement the# above approach# Initialise maximum possible# length of subsequencemax_length = 0# Store elements to compare# max_length with its size# and change the value of# max_length accordinglystore = []# Store the elements of the# longest subsequenceans = []# Function to find the length# of longest subsequencedef find_max_length(arr, index, sum, k): global max_length sum = sum + arr[index] store.append(arr[index]) if (sum == k): if (max_length < len(store)): # Update max_length max_length = len(store) # Store the subsequence # elements ans = store for i in range ( index + 1, len(arr)): if (sum + arr[i] <= k): # Recursively proceed # with obtained sum find_max_length(arr, i, sum, k) # popping elements # from back # of vector store store.pop() # if sum > 0 then we don't # required thatsubsequence # so return and continue # with earlier elements else: return returndef longestSubsequence(arr, n, k): # Sort the given array arr.sort() # Traverse the array for i in range (n): # If max_length is already # greater than or equal # than remaining length if (max_length >= n - i): break store.clear() find_max_length(arr, i, 0, k) return max_length# Driver codeif __name__ == "__main__": arr = [-3, 0, 1, 1, 2] n = len(arr) k = 1 print (longestSubsequence(arr, n, k)) # This code is contributed by Chitranayal |
C#
// C# program to implement the// above approachusing System;using System.Collections.Generic;class GFG{// Initialise maximum possible// length of subsequencestatic int max_length = 0;// Store elements to compare// max_length with its size// and change the value of// max_length accordinglystatic List<int> store = new List<int>();// Store the elements of the// longest subsequencestatic List<int> ans = new List<int>();// Function to find the length// of longest subsequencestatic void find_max_length(int []arr, int index, int sum, int k){ sum = sum + arr[index]; store.Add(arr[index]); if (sum == k) { if (max_length < store.Count) { // Update max_length max_length = store.Count; // Store the subsequence // elements ans = store; } } for(int i = index + 1; i < arr.Length; i++) { if (sum + arr[i] <= k) { // Recursively proceed // with obtained sum find_max_length(arr, i, sum, k); // popping elements // from back // of vector store store.RemoveAt(store.Count - 1); } // If sum > 0 then we don't // required thatsubsequence // so return and continue // with earlier elements else return; } return;}static int longestSubsequence(int []arr, int n, int k){ // Sort the given array Array.Sort(arr); // Traverse the array for(int i = 0; i < n; i++) { // If max_length is already // greater than or equal // than remaining length if (max_length >= n - i) break; store.Clear(); find_max_length(arr, i, 0, k); } return max_length;}// Driver codepublic static void Main(String[] args){ int []arr = { -3, 0, 1, 1, 2 }; int n = arr.Length; int k = 1; Console.Write(longestSubsequence(arr, n, k));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript Program to implement the// above approach// Initialise maximum possible// length of subsequencelet max_length = 0;// Store elements to compare// max_length with its size// and change the value of// max_length accordinglylet store = [];// Store the elements of the// longest subsequencelet ans = [];// Function to find the length// of longest subsequencefunction find_max_length(arr,index,sum,k){ sum = sum + arr[index]; store.push(arr[index]); if (sum == k) { if (max_length < store.length) { // Update max_length max_length = store.length; // Store the subsequence // elements ans = store; } } for (let i = index + 1; i < arr.length; i++) { if (sum + arr[i] <= k) { // Recursively proceed // with obtained sum find_max_length(arr, i, sum, k); // popping elements // from back // of vector store store.pop(); } // if sum > 0 then we don't // required thatsubsequence // so return and continue // with earlier elements else return; } return;}function longestSubsequence(arr, n, k){ // Sort the given array arr.sort(function(a,b){return a-b;}); // Traverse the array for (let i = 0; i < n; i++) { // If max_length is already // greater than or equal // than remaining length if (max_length >= n - i) break; store=[]; find_max_length(arr, i, 0, k); } return max_length;}// Driver codelet arr = [-3, 0, 1, 1, 2 ];let n = arr.length;let k = 1;document.write(longestSubsequence(arr,n, k));// This code is contributed by avanitrachhadiya2155</script> |
Output:
5
Time Complexity: O(N3)
Auxiliary Space: O(N)
Dynamic Programming Approach: Refer to this article for a further optimized approach to solve the problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
