Given an array arr[] of size N such that the sum of all the array elements does not exceed N, and array queries[] containing Q queries. For each query, the task is to find if there is a subset of the array whose sum is the same as queries[i].
Examples:
Input: arr[] = {1, 0, 0, 0, 0, 2, 3}, queries[] = {3, 7, 6}
Output:
Possible
Not Possible
Possible
Explanation: 3 is spossible. 6 can be obtained by the subset {1, 2, 3}
7 is greater than the sum of all array elements.Input: arr[] = {0, 1, 2}, queries[] = {1, 2, 3, 0}
Output:
Possible
Possible
Possible
Possible
Explanation: All the sums can be obtained by using the elements.
Approach: The problem can be solved using the approach as in the subset sum problem.
However, the time complexity can be reduced using the fact that the sum can be at most N. As the sum can be at most N, it can be proved that there are at most √2N unique positive elements where all have a frequency of 1.
Say there are √2N unique positive elements starting from 1 to √2N.
Therefore the sum of those numbers is N + √(N/2).
This sum is more than N itself. So there can be at most √2N unique elements.
The above fact can be used and implemented in dynamic programming. Using coordinate compression all those unique elements can be stored in minimum space.
For each element check what is the minimum contribution of that element to achieve a sum j (j in the range [0, N]) or if it is not possible to achieve the sum j. The contribution of each item (say i) depends on the contribution of the other smaller items till the sum (j – i).
Follow the image shown below to understand better the difference of unused states for normal subset and when the sum is N at max:
Comparison:
Say the arr[] = {1, 2, 2, 2, 3, 3}. (Here sum is greater, so does not follow the condition of sum at most N. But here unique elements maintain the threshold. That’s why it is used here just for understanding purpose)
Red cells signify the useless states, these are much more in traditional algorithm than optimized one.
Traditional Subset-Sum vs Frequency Optimized DP, Useless States
Follow the steps mentioned below to implement the approach;
- Use coordinate compression on all the unique elements.
- Build a 2D dp[][] array where dp[i][j] stores the contribution of ith item to get sum j. (If it is not possible then store –1, and if ith item is not needed then store 0 in dp[i][j]).
- Iterate from i = 0 to the maximum element:
- Iterate for j = 0 to N:
- If the value of dp[i][j-arr[i]] + 1 < dp[i][j] then update it.
- Otherwise, keep it as it was.
- Iterate for j = 0 to N:
- Then iterate from i = 0 to Q:
- Check if that sum (query[i])is possible or not.
- It is not possible if it exceeds the array sum or all the elements together cannot get a certain sum i.e. dp[len][query[i]] = -1. (len is total number of unique elements)
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find if the queries// are possible or notvoid findSol(vector<int>& arr, vector<int>& queries){ int s = 0; // Calculating sum of array for (auto& item : arr) { s += item; } // Coordinate compression, // make frequency-value pairs map<int, int> mp; for (auto& item : arr) { mp[item]++; } vector<int> val, freq; // Frequency mapping for (auto& x : mp) { val.push_back(x.first); freq.push_back(x.second); } int len = val.size(); vector<vector<int> > dp(len + 1, vector<int>( s + 1, 0)); for (int j = 1; j <= s; ++j) { dp[0][j] = -1; } // Loop to build the dp[][] for (int i = 1; i <= len; ++i) { for (int j = 1; j <= s; ++j) { int v = val[i - 1]; int f = freq[i - 1]; if (dp[i - 1][j] != -1) { dp[i][j] = 0; } else if (j >= v && dp[i][j - v] != -1 && dp[i][j - v] + 1 <= f) { dp[i][j] = dp[i][j - v] + 1; } else { dp[i][j] = -1; } } } // Answer queries for (auto& q : queries) { if (q > s || dp[len][q] == -1) { cout << "Not Possible" << endl; } else { cout << "Possible" << endl; } }}// Driver Codeint main(){ vector<int> arr = { 1, 0, 0, 0, 0, 2, 3 }; vector<int> queries = { 3, 7, 6 }; // Function call findSol(arr, queries); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG{ // Function to find if the queries// are possible or notstatic void findSol(ArrayList<Integer> arr, ArrayList<Integer> queries){ int s = 0; // Calculating sum of array for (Integer item : arr) { s += item; } // Coordinate compression, // make frequency-value pairs HashMap<Integer, Integer> mp = new HashMap<>(); for (Integer item : arr) { if(mp.containsKey(item)) mp.put(item,mp.get(item)+1); else mp.put(item,1); } ArrayList<Integer> val = new ArrayList<Integer>(); ArrayList<Integer> freq = new ArrayList<Integer>(); // Frequency mapping for (Map.Entry<Integer,Integer> x : mp.entrySet()) { val.add(x.getKey()); freq.add(x.getValue()); } int len = val.size(); int dp[][] = new int[len+1][s+1]; for (int j = 1; j <= s; ++j) { dp[0][j] = -1; } // Loop to build the dp[][] for (int i = 1; i <= len; ++i) { for (int j = 1; j <= s; ++j) { int v = val.get(i - 1); int f = freq.get(i - 1); if (dp[i - 1][j] != -1) { dp[i][j] = 0; } else if (j >= v && dp[i][j - v] != -1 && dp[i][j - v] + 1 <= f) { dp[i][j] = dp[i][j - v] + 1; } else { dp[i][j] = -1; } } } // Answer queries for(Integer q:queries) { if (q > s || dp[len][q] == -1) { System.out.println("Not Possible"); } else { System.out.println("Possible"); } }} // Driver Codepublic static void main(String[] args){ ArrayList<Integer> arr = new ArrayList<Integer>( Arrays.asList(1, 0, 0, 0, 0, 2, 3 )); ArrayList<Integer> queries = new ArrayList<Integer>( Arrays.asList(3, 7, 6 )); // Function call findSol(arr, queries);}}// This code is contributed by Pushpesh Raj. |
Python3
# Python3 code to implement the approach# Function to find if the queries# are possible or notdef findSol(arr, queries): # calculating sum of array s = sum(arr) # Coordinate compression, # make frequency-value pairs mp = dict() for item in arr: if item not in mp: mp[item] = 1 else: mp[item] += 1 val = [] freq = [] # Frequency mapping for x in mp: val.append(x) freq.append(mp[x]) len_ = len(val) dp = [[0 for i in range(s + 1)] for j in range(len_ + 1)] for j in range(1, s + 1): dp[0][j] = -1 # Loop to build dp[][] for i in range(1, len_ + 1): for j in range(1, s + 1): v = val[i - 1] f = freq[i - 1] if dp[i - 1][j] != -1: dp[i][j] = 0 elif j >= 0 and dp[i][j - v] != -1 and dp[i][j - v] + 1 <= f: dp[i][j] = dp[i][j - v] + 1 else: dp[i][j] = -1 # Answer queries for q in queries: if q > s or dp[len_][q] == -1: print("Not Possible") else: print("Possible")# Driver Codearr = [1, 0, 0, 0, 0, 2, 3]queries = [3, 7, 6]# Function callfindSol(arr, queries)# This code is contributed by phasing17 |
C#
// C# program to implement above approachusing System;using System.Collections.Generic;class GFG{ // Function to find if the queries // are possible or not public static void findSol(List<int> arr, List<int> queries) { int s = 0; // Calculating sum of array foreach (int item in arr){ s += item; } // Coordinate compression, // make frequency-value pairs SortedDictionary<int, int> mp = new SortedDictionary<int, int>(); foreach (int item in arr) { if(mp.ContainsKey(item)){ mp[item] = mp[item] + 1; }else{ mp.Add(item, 1); } } List<int> val = new List<int>(); List<int> freq = new List<int>(); // Frequency mapping foreach (KeyValuePair<int,int> x in mp) { val.Add(x.Key); freq.Add(x.Value); } int len = val.Count; int[,] dp = new int[len+1, s+1]; for (int j = 1; j <= s; ++j) { dp[0, j] = -1; } // Loop to build the dp[][] for (int i = 1; i <= len; ++i) { for (int j = 1; j <= s; ++j) { int v = val[i - 1]; int f = freq[i - 1]; if (dp[i - 1, j] != -1) { dp[i, j] = 0; } else if (j >= v && dp[i, j - v] != -1 && dp[i, j - v] + 1 <= f) { dp[i, j] = dp[i, j - v] + 1; } else{ dp[i, j] = -1; } } } // Answer queries foreach(int q in queries) { if (q > s || dp[len, q] == -1) { Console.Write("Not Possible\n"); } else { Console.Write("Possible\n"); } } } // Driver Code public static void Main(string[] args){ List<int> arr = new List<int>{ 1, 0, 0, 0, 0, 2, 3 }; List<int> queries = new List<int>{ 3, 7, 6 }; // Function call findSol(arr, queries); }}// This code is contributed by subhamgoyal2014. |
Javascript
<script>// JavaScript code to implement the approach// Function to find if the queries// are possible or notfunction findSol(arr,queries){ let s = 0; // Calculating sum of array for (let item of arr) { s += item; } // Coordinate compression, // make frequency-value pairs let mp = new Map(); for (let item of arr) { if(mp.has(item)) mp.set(item,mp.get(item)+1); else mp.set(item,1); } let val = [], freq = []; // Frequency mapping for (let [x,y] of mp) { val.push(x); freq.push(y); } let len = val.length; let dp = new Array(len + 1).fill(0).map(()=>new Array(s+1).fill(0)); for (let j = 1; j <= s; ++j) { dp[0][j] = -1; } // Loop to build the dp[][] for (let i = 1; i <= len; ++i) { for (let j = 1; j <= s; ++j) { let v = val[i - 1]; let f = freq[i - 1]; if (dp[i - 1][j] != -1) { dp[i][j] = 0; } else if (j >= v && dp[i][j - v] != -1 && dp[i][j - v] + 1 <= f) { dp[i][j] = dp[i][j - v] + 1; } else { dp[i][j] = -1; } } } // Answer queries for (let q of queries) { if (q > s || dp[len][q] == -1) { console.log("Not Possible"); } else { console.log("Possible"); } }}// Driver Codelet arr = [ 1, 0, 0, 0, 0, 2, 3 ];let queries = [ 3, 7, 6 ];// Function callfindSol(arr, queries);// This code is contributed by shinjanpatra</script> |
Possible Not Possible Possible
Time Complexity: O(N * √N)
Auxiliary Space: O(N * √N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
