Given an array arr[], the task is to find the sum of a subsequence that forms a perfect square. If there are multiple subsequences having a sum equal to a perfect square, print the maximum sum.
Explanation:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Output: 36
Explanation:
Maximum possible sum which is a perfect square that can be obtained from the array is 36 obtained from the subsequence {1, 5, 6, 7, 8, 9}.
Input: arr[] = {9, 10}
Output: 9
Naive Approach: Generate all the possible subsequences of a given array and for each subsequence, check if its sum is a Perfect Square. If such a sum is found, update the maximum sum. Finally, print the maximum sum obtained.
Time Complexity: O(N * 2N)
Auxiliary Space: O(N)
Efficient Approach:
The above approach can be optimized by using Dynamic Programming approach.
Follow the steps given below:
- Calculate the sum of the array.
- Iterate k in the range [?sum, 0] and check if any subsequence exists with that sum k2. For every k, follow the steps below:
- Initialize boolean matrix subset[][] of dimensions N * sum, where sum denotes the current value of k2.
- subset[i][j] denotes whether a subsequence of size i with sum j exists or not.
- Initialize first column and first row as true and false respectively of subset[][].
- Run two nested loops, outer from i in the range [1, N] and inner j in the range [1, sum]to fill the subset[][] matrix in bottom up manner based on the following conditions:
- if (j < arr[i – 1]), then subset[i][j] = subset[i – 1][j]
- if (j >= arr[i – 1]), then subset[i][j] = subset[i – 1][j] || subset[i – 1][j – arr[i – 1]]
- Finally, return the subset[n][sum].
- The first k for which subset[n][k] is true, gives the required maximum possible subsequence sum k2.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; bool isSubsetSum( int arr[], int n, int sum) { bool subset[n + 1][sum + 1]; // If sum is 0, then answer is true for ( int i = 0; i <= n; i++) subset[i][0] = true ; // If sum is not 0 and arr[] is empty, // then answer is false for ( int i = 1; i <= sum; i++) subset[0][i] = false ; // Fill the subset table in bottom up manner for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i][j] = subset[i - 1][j]; if (j >= arr[i - 1]) subset[i][j] = subset[i - 1][j] || subset[i - 1][j - arr[i - 1]]; } } return subset[n][sum]; } // Function to find the sum int findSum( int * arr, int n) { int sum = 0; // Find sum of all values for ( int i = 0; i < n; i++) { sum += arr[i]; } int val = sqrt (sum); for ( int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findSum(arr, n) << endl; return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ static boolean isSubsetSum( int arr[], int n, int sum) { boolean [][] subset = new boolean [n + 1 ][sum + 1 ]; // If sum is 0, then answer is true for ( int i = 0 ; i <= n; i++) subset[i][ 0 ] = true ; // If sum is not 0 and arr[] is empty, // then answer is false for ( int i = 1 ; i <= sum; i++) subset[ 0 ][i] = false ; // Fill the subset table in bottom up manner for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= sum; j++) { if (j < arr[i - 1 ]) subset[i][j] = subset[i - 1 ][j]; if (j >= arr[i - 1 ]) subset[i][j] = subset[i - 1 ][j] || subset[i - 1 ][j - arr[i - 1 ]]; } } return subset[n][sum]; } // Function to find the sum static int findSum( int [] arr, int n) { int sum = 0 ; // Find sum of all values for ( int i = 0 ; i < n; i++) { sum += arr[i]; } int val = ( int )Math.sqrt(sum); for ( int i = val; i >= 0 ; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0 ; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; int n = arr.length; System.out.println(findSum(arr, n)); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach import math def isSubsetSum(arr, n, sum ): subset = [ [ True for x in range ( sum + 1 ) ] for y in range (n + 1 ) ] # If sum is 0, then answer is true for i in range (n + 1 ): subset[i][ 0 ] = True # If sum is not 0 and arr[] is empty, # then answer is false for i in range ( 1 , sum + 1 ): subset[ 0 ][i] = False # Fill the subset table in bottom up manner for i in range ( 1 , n + 1 ): for j in range ( 1 , sum + 1 ): if (j < arr[i - 1 ]): subset[i][j] = subset[i - 1 ][j] if (j > = arr[i - 1 ]): subset[i][j] = (subset[i - 1 ][j] or subset[i - 1 ][j - arr[i - 1 ]]) return subset[n][ sum ] # Function to find the sum def findSum(arr, n): sum = 0 # Find sum of all values for i in range (n): sum + = arr[i] val = int (math.sqrt( sum )) for i in range (val, - 1 , - 1 ): if (isSubsetSum(arr, n, i * i)): # Return the value; return i * i return 0 # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] n = len (arr) print (findSum(arr, n)) # This code is contributed by chitranayal |
C#
// C# program to implement // the above approach using System; class GFG{ static bool isSubsetSum( int []arr, int n, int sum) { bool [,] subset = new bool [n + 1, sum + 1]; // If sum is 0, then answer is true for ( int i = 0; i <= n; i++) subset[i, 0] = true ; // If sum is not 0 and []arr is empty, // then answer is false for ( int i = 1; i <= sum; i++) subset[0, i] = false ; // Fill the subset table in bottom up manner for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i, j] = subset[i - 1, j]; if (j >= arr[i - 1]) subset[i, j] = subset[i - 1, j] || subset[i - 1, j - arr[i - 1]]; } } return subset[n, sum]; } // Function to find the sum static int findSum( int [] arr, int n) { int sum = 0; // Find sum of all values for ( int i = 0; i < n; i++) { sum += arr[i]; } int val = ( int )Math.Sqrt(sum); for ( int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0; } // Driver code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = arr.Length; Console.WriteLine(findSum(arr, n)); } } // This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript program to implement // the above approach function isSubsetSum(arr, n, sum) { let subset = new Array(n + 1); for ( var i = 0; i < subset.length; i++) { subset[i] = new Array(2); } // If sum is 0, then answer is true for (let i = 0; i <= n; i++) subset[i][0] = true ; // If sum is not 0 and arr[] is empty, // then answer is false for (let i = 1; i <= sum; i++) subset[0][i] = false ; // Fill the subset table in bottom up manner for (let i = 1; i <= n; i++) { for (let j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i][j] = subset[i - 1][j]; if (j >= arr[i - 1]) subset[i][j] = subset[i - 1][j] || subset[i - 1][j - arr[i - 1]]; } } return subset[n][sum]; } // Function to find the sum function findSum(arr, n) { let sum = 0; // Find sum of all values for (let i = 0; i < n; i++) { sum += arr[i]; } let val = Math.floor(Math.sqrt(sum)); for (let i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0; } // Driver Code let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; let n = arr.length; document.write(findSum(arr, n)); </script> |
36
Time Complexity: O(N * SUM)
Auxiliary Space: O(N * SUM)
Efficient approach : Space optimization
In previous approach the current value subset[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D array subset of size sum+1 and initialize it with false.
- Set a base case and initialize subset[0] = True.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- At last return the final answer stored in subset[sum].
Implementation:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; bool isSubsetSum( int arr[], int n, int sum) { bool subset[sum + 1]; memset (subset, false , sizeof (subset)); // If sum is 0, then answer is true subset[0] = true ; // iterative over subproblems to get the // current value from previous computations for ( int i = 0; i < n; i++) { for ( int j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // return final answer return subset[sum]; } // Function to find the sum int findSum( int * arr, int n) { int sum = 0; // Find sum of all values for ( int i = 0; i < n; i++) { sum += arr[i]; } int val = sqrt (sum); for ( int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof (arr) / sizeof (arr[0]); // function call cout << findSum(arr, n) << endl; return 0; } // this code is contributed by bhardwajji |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG { static boolean isSubsetSum( int [] arr, int n, int sum) { boolean [] subset = new boolean [sum + 1 ]; Arrays.fill(subset, false ); // If sum is 0, then answer is true subset[ 0 ] = true ; // iterative over subproblems to get the // current value from previous computations for ( int i = 0 ; i < n; i++) { for ( int j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // return final answer return subset[sum]; } // Function to find the sum static int findSum( int [] arr, int n) { int sum = 0 ; // Find sum of all values for ( int i = 0 ; i < n; i++) { sum += arr[i]; } int val = ( int ) Math.sqrt(sum); for ( int i = val; i >= 0 ; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0 ; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; int n = arr.length; // function call System.out.println(findSum(arr, n)); } } |
Python3
import math # Function to check if a subset with # given sum exists in the array def isSubsetSum(arr, n, target): # Initialize a boolean array # subset of size target+1 and # fill it with False subset = [ False ] * (target + 1 ) # Set subset[0] to True as a subset # with sum 0 always exists subset[ 0 ] = True # Iterate through all elements # in the array for i in range (n): # Iterate backwards through the # subset array starting from target # and going down to arr[i] # This is done to avoid recomputing # subsets that have already been checked for j in range (target, arr[i] - 1 , - 1 ): # If subset[j-arr[i]] is True, then # a subset with sum j-arr[i] exists # Therefore, a subset with sum j can # be formed by adding arr[i] to this subset subset[j] = subset[j] or subset[j - arr[i]] # Return True if a subset with the # target sum exists, else False return subset[target] # Function to find the largest perfect square # less than or equal to the sum of all elements # in the array def findSum(arr, n): # Find the sum of all elements # in the array total_sum = sum (arr) # Find the square root of the sum of all # elements and cast it to an integer val = int (math.sqrt(total_sum)) # Iterate backwards from the square # root of the sum of all elements for i in range (val, - 1 , - 1 ): # If a subset with sum i*i exists, # return i*i if isSubsetSum(arr, n, i * i): return i * i # If no perfect square is found, # return 0 return 0 # Driver Code if __name__ = = "__main__" : # Initialize an array of integers arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] # Find the length of the array n = len (arr) # Call the findSum function and # print the result print (findSum(arr, n)) |
C#
using System; public class GFG { static bool isSubsetSum( int [] arr, int n, int sum) { bool [] subset = new bool [sum + 1]; Array.Fill(subset, false ); // If sum is 0, then answer is true subset[0] = true ; // iterative over subproblems to get the // current value from previous computations for ( int i = 0; i < n; i++) { for ( int j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // return final answer return subset[sum]; } static int findSum( int [] arr, int n) { int sum = 0; // Find sum of all values for ( int i = 0; i < n; i++) { sum += arr[i]; } int val = ( int )Math.Sqrt(sum); for ( int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0; } public static void Main() { int [] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = arr.Length; // function call Console.WriteLine(findSum(arr, n)); } } |
Javascript
function isSubsetSum(arr, n, sum) { const subset = new Array(sum + 1).fill( false ); // If sum is 0, then the answer is true subset[0] = true ; // Iterate over subproblems to get the current value from previous computations for (let i = 0; i < n; i++) { for (let j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // Return the final answer return subset[sum]; } function findSum(arr, n) { let sum = 0; // Find the sum of all values for (let i = 0; i < n; i++) { sum += arr[i]; } const val = Math.floor(Math.sqrt(sum)); for (let i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // Return the value return i * i; } } return 0; } // Driver Code const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; const n = arr.length; // Function call console.log(findSum(arr, n)); |
36
Time Complexity: O(N * SUM)
Auxiliary Space: O(SUM)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!