Subset Sum Problem using Dynamic Programming with space optimization to linear
Idea:
In previous approach of dynamic programming we have derive the relation between states as given below:
if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]If we observe that for calculating current dp[i][j] state we only need previous row dp[i-1][j] or dp[i-1][j-set[i-1]].
There is no need to store all the previous states just one previous state is used to compute result.
Approach:
- Define two arrays prev and curr of size Sum+1 to store the just previous row result and current row result respectively.
- Once curr array is calculated then curr becomes our prev for the next row.
- When all rows are processed the answer is stored in prev array.
Implementation of the above approach:
// A Dynamic Programming solution
// for subset sum problem with space optimization
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is a subset of set[]
// with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
vector<bool> prev(sum + 1);
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
prev[0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
prev[i] = false;
// curr array to store the current row result generated
// with help of prev array
vector<bool> curr(sum + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1])
curr[j] = prev[j];
if (j >= set[i - 1])
curr[j] = prev[j] || prev[j - set[i - 1]];
}
// now curr becomes prev for i+1 th element
prev = curr;
}
return prev[sum];
}
// Driver code
int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
cout << "Found a subset with given sum";
else
cout << "No subset with given sum";
return 0;
}
// This code is contributed by Hem Kishan
import java.util.Arrays;
public class SubsetSum {
// Returns true if there is a subset of set[]
// with a sum equal to the given sum
static boolean isSubsetSum(int[] set, int n, int sum) {
boolean[] prev = new boolean[sum + 1];
// If the sum is 0, the answer is true
for (int i = 0; i <= n; i++)
prev[0] = true;
// If the sum is not 0 and the set is empty,
// the answer is false
for (int i = 1; i <= sum; i++)
prev[i] = false;
// curr array to store the current row result generated
// with the help of the prev array
boolean[] curr = new boolean[sum + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1])
curr[j] = prev[j];
if (j >= set[i - 1])
curr[j] = prev[j] || prev[j - set[i - 1]];
}
// now curr becomes prev for (i + 1)th element
prev = Arrays.copyOf(curr, curr.length);
}
return prev[sum];
}
// Driver code
public static void main(String[] args) {
int[] set = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum))
System.out.println("Found a subset with the given sum");
else
System.out.println("No subset with the given sum");
}
}
// This code is contributed by shivamgupta0987654321
# Returns True if there is a subset of set[]
# with a sum equal to the given sum
def isSubsetSum(nums, n, sum):
# Create a list to store the previous row result
prev = [False] * (sum + 1)
# If sum is 0, then the answer is True
prev[0] = True
# If sum is not 0 and the set is empty,
# then the answer is False
for i in range(1, n + 1):
curr = [False] * (sum + 1)
for j in range(1, sum + 1):
if j < nums[i - 1]:
curr[j] = prev[j]
if j >= nums[i - 1]:
curr[j] = prev[j] or prev[j - nums[i - 1]]
# Now curr becomes prev for (i+1)-th element
prev = curr
return prev[sum]
# Driver code
if __name__ == "__main__":
nums = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(nums)
if isSubsetSum(nums, n, sum_value):
print("Found a subset with the given sum")
else:
print("No subset with the given sum")
using System;
class Program
{
// Returns true if there is a subset of set[]
// with sum equal to given sum
static bool IsSubsetSum(int[] set, int n, int sum)
{
// Create a 2D array 'dp' with dimensions (n+1) x (sum+1)
bool[,] dp = new bool[n + 1, sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
dp[i, 0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
dp[0, i] = false;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if (j < set[i - 1])
dp[i, j] = dp[i - 1, j];
if (j >= set[i - 1])
dp[i, j] = dp[i - 1, j] || dp[i - 1, j - set[i - 1]];
}
}
return dp[n, sum];
}
static void Main()
{
int[] set = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.Length;
if (IsSubsetSum(set, n, sum))
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}
// Returns true if there is a subset of set[]
// with sum equal to given sum
function isSubsetSum(set, n, sum) {
// Initialize a matrix to store subproblem results
let prev = new Array(sum + 1).fill(false);
// If sum is 0, then answer is true
prev[0] = true;
// curr array to store the current row result generated
// with help of prev array
let curr = [...prev];
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= sum; j++) {
if (j < set[i - 1]) {
curr[j] = prev[j];
}
if (j >= set[i - 1]) {
curr[j] = prev[j] || prev[j - set[i - 1]];
}
}
// now curr becomes prev for i+1 th element
prev = [...curr];
}
return prev[sum];
}
// Driver code
let set = [3, 34, 4, 12, 5, 2];
let sum = 9;
let n = set.length;
if (isSubsetSum(set, n, sum)) {
console.log("Found a subset with given sum");
} else {
console.log("No subset with given sum");
}
Output
Found a subset with given sum
Complexity Analysis:
- Time Complexity: O(sum * n), where n is the size of the array.
- Auxiliary Space: O(sum), as the size of the 1-D array is sum+1.
Related Articles:
Subset Sum Problem
Given a set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that add up to 30.
Contact Us