Unique subsequences of length K with given sum
Given an array arr[] of N integers and two numbers K and S, the task is to print all the subsequence of length K with the sum S.
Examples:
Input: N = 5, K = 3, S = 20, arr[] = {4, 6, 8, 2, 12}
Output:
{6, 2, 12}
Explanation:
Only one subsequence of size 3 with a sum 20 is possible i.e., {6, 2, 12} and sum is 6 + 2 + 12 = 20
Input: N = 10, K = 5, S = 25, arr[] = {2, 4, 6, 8, 10, 12, 1, 2, 5, 7}
Output:
{10, 1, 2, 5, 7}
{4, 8, 1, 5, 7}
{4, 8, 10, 1, 2}
{4, 6, 12, 1, 2}
{4, 6, 8, 2, 5}
{2, 10, 1, 5, 7}
{2, 8, 12, 1, 2}
{2, 6, 10, 2, 5}
{2, 6, 8, 2, 7}
{2, 4, 12, 2, 5}
{2, 4, 10, 2, 7}
{2, 4, 8, 10, 1}
{2, 4, 6, 12, 1}
{2, 4, 6, 8, 5}
Approach: The idea is to use Backtracking to print all the subsequence with given sum S. Below are the steps:
- Iterate for all the value of the array arr[] and do the following:
- If we include the current element in the resultant subsequence then, decrement K and the above value of current element to the sum S.
- Recursively iterate from next index of the element to the end of the array to find the resultant subsequence.
- If K is 0 and S is 0 then we got our one of the resultant subsequence of length K and sum S, print this subsequence and backtrack for the next resulting subsequence.
- If we doesn’t include the current element then, find the resultant subsequence by excluding the current element and repeating the above procedure for the rest of the element in the array.
- Resultant array in the steps 3 will give all the possible subsequence of length K with given sum S.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find all the subsequences// of a given length and having sum Svoid comb(int* arr, int len, int r, int ipos, int* op, int opos, int sum){ // Termination condition if (opos == r) { int sum2 = 0; for (int i = 0; i < opos; i++) { // Add value to sum sum2 = sum2 + op[i]; } // Check if the resultant sum // equals to target sum if (sum == sum2) { // If true for (int i = 0; i < opos; i++) // Print resultant array cout << op[i] << ", "; cout << endl; } // End this recursion stack return; } if (ipos < len) { // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos, sum); op[opos] = arr[ipos]; // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos + 1, sum); }}// Driver Codeint main(){ // Given array int arr[] = { 4, 6, 8, 2, 12 }; int K = 3; int S = 20; int N = sizeof(arr) / sizeof(arr[0]); // To store the subsequence int op[N] = { 0 }; // Function Call comb(arr, N, K, 0, op, 0, S); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find all the subsequences// of a given length and having sum Sstatic void comb(int []arr, int len, int r, int ipos, int[] op, int opos, int sum){ // Termination condition if (opos == r) { int sum2 = 0; for(int i = 0; i < opos; i++) { // Add value to sum sum2 = sum2 + op[i]; } // Check if the resultant sum // equals to target sum if (sum == sum2) { // If true for(int i = 0; i < opos; i++) // Print resultant array System.out.print(op[i] + ", "); System.out.println(); } // End this recursion stack return; } if (ipos < len) { // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos, sum); op[opos] = arr[ipos]; // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos + 1, sum); }}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 4, 6, 8, 2, 12 }; int K = 3; int S = 20; int N = arr.length; // To store the subsequence int op[] = new int[N]; // Function Call comb(arr, N, K, 0, op, 0, S);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approach# Function to find all the subsequences # of a given length and having sum S def comb(arr, Len, r, ipos, op, opos, Sum): # Termination condition if (opos == r): sum2 = 0 for i in range(opos): # Add value to sum sum2 = sum2 + op[i] # Check if the resultant sum # equals to target sum if (Sum == sum2): # If true for i in range(opos): # Print resultant array print(op[i], end = ", ") print() # End this recursion stack return if (ipos < Len): # Check all the combinations # using backtracking comb(arr, Len, r, ipos + 1, op, opos, Sum) op[opos] = arr[ipos] # Check all the combinations # using backtracking comb(arr, Len, r, ipos + 1, op, opos + 1, Sum)# Driver codeif __name__ == '__main__': # Given array arr = [ 4, 6, 8, 2, 12 ] K = 3 S = 20 N = len(arr) # To store the subsequence op = [0] * N # Function call comb(arr, N, K, 0, op, 0, S)# This code is contributed by himanshu77 |
C#
// C# program for the above approachusing System;class GFG{// Function to find all the subsequences// of a given length and having sum Sstatic void comb(int []arr, int len, int r, int ipos, int[] op, int opos, int sum){ // Termination condition if (opos == r) { int sum2 = 0; for(int i = 0; i < opos; i++) { // Add value to sum sum2 = sum2 + op[i]; } // Check if the resultant sum // equals to target sum if (sum == sum2) { // If true for(int i = 0; i < opos; i++) // Print resultant array Console.Write(op[i] + ", "); Console.WriteLine(); } // End this recursion stack return; } if (ipos < len) { // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos, sum); op[opos] = arr[ipos]; // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos + 1, sum); }}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = { 4, 6, 8, 2, 12 }; int K = 3; int S = 20; int N = arr.Length; // To store the subsequence int []op = new int[N]; // Function call comb(arr, N, K, 0, op, 0, S);}}// This code is contributed by amal kumar choubey |
Javascript
<script>// JavaScript program for the above approach// Function to find all the subsequences// of a given length and having sum Sfunction comb(arr, len, r, ipos, op, opos, sum){ // Termination condition if (opos == r) { let sum2 = 0; for(let i = 0; i < opos; i++) { // Add value to sum sum2 = sum2 + op[i]; } // Check if the resultant sum // equals to target sum if (sum == sum2) { // If true for(let i = 0; i < opos; i++) // Print resultant array document.write(op[i] + ", "); document.write(); } // End this recursion stack return; } if (ipos < len) { // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos, sum); op[opos] = arr[ipos]; // Check all the combinations // using backtracking comb(arr, len, r, ipos + 1, op, opos + 1, sum); }} // Driver Code // Given array let arr = [ 4, 6, 8, 2, 12 ]; let K = 3; let S = 20; let N = arr.length; // To store the subsequence let op = Array.from({length: N}, (_, i) => 0); // Function Call comb(arr, N, K, 0, op, 0, S);// This code is contributed by sanjoy_62.</script> |
Output:
6, 2, 12,
Time Complexity: O(2^N * K)
Auxiliary Space: O(N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
