A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. For example, 1, 3, 6, 13, 27, 52 is such subsequence.
Now, given a superincreasing sequence S and the sum of a subsequence of this sequence, the task is to find the subsequence.
Examples:
Input: S[] = {17, 25, 46, 94, 201, 400}, sum = 272
Output: 25 46 201
25 + 46 + 201 = 272Input: S[] = {1, 2, 4, 8, 16}, sum = 12
Output: 4 8
Brute Force Approach :
- Generate all possible subsequences of the array
- For each subsequence, check if the sum of its elements is equal to the given sum
- Return the subsequence that satisfies the condition, or null if no such subsequence exists
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;void findSubSeq(int arr[], int n, int sum){ // Generate all possible subsequences for (int i = 0; i < (1 << n); i++) { vector<int> subSeq; for (int j = 0; j < n; j++) { // Check if the jth element of the array is // included in the current subsequence if (i & (1 << j)) { subSeq.push_back( arr[j]); // Add the jth element to the // current subsequence } } // Check if the sum of the current subsequence // equals to the given sum int currentSum = accumulate(subSeq.begin(), subSeq.end(), 0); // Calculate the sum of the // current subsequence if (currentSum == sum) { // If the sum is equal to // the given sum, print the // subsequence and return for (int k = 0; k < subSeq.size(); k++) { cout << subSeq[k] << " "; } return; } } // No subsequence found cout << "null";}int main(){ int arr[] = { 17, 25, 46, 94, 201, 400 }; int n = sizeof(arr) / sizeof(int); int sum = 272; findSubSeq(arr, n, sum); // Find a subsequence of the // array with the given sum return 0;} |
Java
// Java code of above approachimport java.io.*;import java.util.*;public class Main { public static void findSubSeq(int[] arr, int n, int sum) { // Generate all possible subsequences for (int i = 0; i < (1 << n); i++) { List<Integer> subSeq = new ArrayList<>(); for (int j = 0; j < n; j++) { // Check if the jth element of the array is // included in the current subsequence if ((i & (1 << j)) != 0) { subSeq.add( arr[j]); // Add the jth element to // the current subsequence } } // Check if the sum of the current subsequence // equals to the given sum int currentSum = 0; for (int k = 0; k < subSeq.size(); k++) { currentSum += subSeq.get(k); } if (currentSum == sum) { // If the sum is equal to the // given sum, print the // subsequence and return for (int k = 0; k < subSeq.size(); k++) { System.out.print(subSeq.get(k) + " "); } return; } } // No subsequence found System.out.println("null"); } public static void main(String[] args) { int[] arr = { 17, 25, 46, 94, 201, 400 }; int n = arr.length; int sum = 272; findSubSeq(arr, n, sum); // Find a subsequence of the array // with the given sum }} |
Python3
def findSubSeq(arr, n, summ): # Generate all possible subsequences for i in range(1 << n): subSeq = [] for j in range(n): # Check if the jth element of the array is included in the current subsequence if (i & (1 << j)) != 0: # Add the jth element to the current subsequence subSeq.append(arr[j]) # Check if the sum of the current subsequence equals to the given sum currentSum = sum(subSeq) if currentSum == summ: # If the sum is equal to the given sum, print the subsequence and return print(subSeq) return # No subsequence found print("null")arr = [17, 25, 46, 94, 201, 400]n = len(arr)summ = 272findSubSeq(arr, n, summ) # Find a subsequence of the array with the given sum |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static void FindSubsequence(int[] arr, int sum) { int n = arr.Length; // Generate all possible subsequences for (int i = 0; i < (1 << n); i++) { List<int> subSeq = new List<int>(); for (int j = 0; j < n; j++) { // Check if the jth element of the array is // included in the current subsequence if ((i & (1 << j)) != 0) { subSeq.Add(arr[j]); // Add the jth element to the current subsequence } } // Check if the sum of the current subsequence // equals the given sum int currentSum = subSeq.Sum(); // Calculate the sum of the current subsequence if (currentSum == sum) { // If the sum is equal to the given sum, print the subsequence and return Console.WriteLine(string.Join(" ", subSeq)); return; } } // No subsequence found Console.WriteLine("null"); } static void Main() { int[] arr = { 17, 25, 46, 94, 201, 400 }; int sum = 272; FindSubsequence(arr, sum); // Find a subsequence of the array with the given sum }} |
Javascript
function findSubSeq(arr, n, summ) {// Generate all possible subsequencesfor (let i = 0; i < (1 << n); i++) {let subSeq = [];for (let j = 0; j < n; j++) {// Check if the jth element of the array is included in the current subsequenceif ((i & (1 << j)) !== 0) {subSeq.push(arr[j]); // Add the jth element to the current subsequence}}// Check if the sum of the current subsequence equals to the given sumlet currentSum = subSeq.reduce((a, b) => a + b, 0);if (currentSum === summ) { // If the sum is equal to the given sum, print the subsequence and returnconsole.log(subSeq);return;}}// No subsequence foundconsole.log("null");}let arr = [17, 25, 46, 94, 201, 400];let n = arr.length;let summ = 272;findSubSeq(arr, n, summ); // Find a subsequence of the array with the given sum |
Output
25 46 201
Time complexity : O(2^n * n)
Auxiliary Space : O(2^n * n)
Approach: This problem can be solved using the greedy technique. Starting from the last element of the array till the first element, there are two cases:
- sum < arr[i]: In this case, the current element cannot be a part of the required subsequence as after including it, the sum of the subsequence will exceed the given sum. So discard the current element.
- sum ? arr[i]: In this case, the current element has to be included in the required subsequence. This is because if the current element is not included then the sum of the previous elements in the array will be smaller than the current element (as it is a superincreasing sequence) which will in turn be smaller than the required sum. So take the current element and update the sum as sum = sum – arr[i].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the required subsequencevoid findSubSeq(int arr[], int n, int sum){ for (int i = n - 1; i >= 0; i--) { // Current element cannot be a part // of the required subsequence if (sum < arr[i]) arr[i] = -1; // Include current element in // the required subsequence // So update the sum else sum -= arr[i]; } // Print the elements of the // required subsequence for (int i = 0; i < n; i++) { // If the current element was // included in the subsequence if (arr[i] != -1) cout << arr[i] << " "; }}// Driver codeint main(){ int arr[] = { 17, 25, 46, 94, 201, 400 }; int n = sizeof(arr) / sizeof(int); int sum = 272; findSubSeq(arr, n, sum); return 0;} |
Java
// Java implementation of the approach class GFG { // Function to find the required subsequence static void findSubSeq(int arr[], int n, int sum) { for (int i = n - 1; i >= 0; i--) { // Current element cannot be a part // of the required subsequence if (sum < arr[i]) arr[i] = -1; // Include current element in // the required subsequence // So update the sum else sum -= arr[i]; } // Print the elements of the // required subsequence for (int i = 0; i < n; i++) { // If the current element was // included in the subsequence if (arr[i] != -1) System.out.print(arr[i] + " "); } } // Driver code public static void main (String[] args) { int arr[] = { 17, 25, 46, 94, 201, 400 }; int n = arr.length; int sum = 272; findSubSeq(arr, n, sum); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to find the required subsequence def findSubSeq(arr, n, sum) : for i in range(n - 1, -1, -1) : # Current element cannot be a part # of the required subsequence if (sum < arr[i]) : arr[i] = -1; # Include current element in # the required subsequence # So update the sum else : sum -= arr[i]; # Print the elements of the # required subsequence for i in range(n) : # If the current element was # included in the subsequence if (arr[i] != -1) : print(arr[i], end = " "); # Driver code if __name__ == "__main__" : arr = [ 17, 25, 46, 94, 201, 400 ]; n = len(arr); sum = 272; findSubSeq(arr, n, sum); # This code is contributed by kanugargng |
C#
// C# implementation of the approachusing System; class GFG { // Function to find the required subsequence static void findSubSeq(int []arr, int n, int sum) { for (int i = n - 1; i >= 0; i--) { // Current element cannot be a part // of the required subsequence if (sum < arr[i]) arr[i] = -1; // Include current element in // the required subsequence // So update the sum else sum -= arr[i]; } // Print the elements of the // required subsequence for (int i = 0; i < n; i++) { // If the current element was // included in the subsequence if (arr[i] != -1) Console.Write(arr[i] + " "); } } // Driver code public static void Main (String[] args) { int []arr = { 17, 25, 46, 94, 201, 400 }; int n = arr.Length; int sum = 272; findSubSeq(arr, n, sum); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Function to find the required subsequencefunction findSubSeq(arr, n, sum) { for (let i = n - 1; i >= 0; i--) { // Current element cannot be a part // of the required subsequence if (sum < arr[i]) arr[i] = -1; // Include current element in // the required subsequence // So update the sum else sum -= arr[i]; } // Print the elements of the // required subsequence for (let i = 0; i < n; i++) { // If the current element was // included in the subsequence if (arr[i] != -1) document.write(arr[i] + " "); }}// Driver codelet arr = [17, 25, 46, 94, 201, 400];let n = arr.length;let sum = 272;findSubSeq(arr, n, sum);// This code is contributed by gfgking.</script> |
Output
25 46 201
Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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!
