Given an array arr[] of length n and an integer target, the task is to find the number of subsets with a sum equal to target.
Examples:
Input: arr[] = [1, 2, 3, 3], target = 6
Output: 3
Explanation: All the possible subsets are [1, 2, 3], [1, 2, 3] and [3, 3]Input: arr[] = [1, 1, 1, 1], target = 1
Output: 4
Explanation: All the possible subsets are [1], [1], [1] and [1]
Try it on GfG Practice
Table of Content
Using Recursion - O(2^n) Time and O(n) Space
The problem is to count the number of subsets of a given array arr[] such that the sum of the elements in each subset equals a specified target. A recursive approach is used to solve this problem by considering two cases for each element in the array:
- Exclude the current element: The element at index i is not included in the subset, and the current sum remains unchanged. This leads to the recursion call countSubsets(i + 1, currentSum, target).
- Include the current element: The element at index i is included in the subset, and the sum is updated as currentSum + arr[i]. This leads to the recursion call countSubsets(i + 1, currentSum + arr[i], target).
Please refer to Count of subsets with sum equal to target using Recursion for implementation.
Using Top - Down Dp (memoization) - O(n*target) Time and O(n*target) Space
If we notice carefully, we can observe that the above recursive solution holds the following two properties of Dynamic Programming:
1. Optimal Substructure: Maximum subsequence length for a given i, j and currentSum , i.e. countSubsets(i, currentSum, target), depends on the optimal solutions of the subproblems countSubsets(i+1, currentSum, target) and countSubsets(i+1, currentSum + arr[i], target). By choosing the total of these optimal substructures, we can efficiently calculate answer.
2. Overlapping Subproblems: While applying a recursive approach in this problem, we notice that certain subproblems are computed multiple times. For example while considering arr = [1, 1, 2, 3] and target = 10, countSubsets(3, 4, 10, arr) computed multiple times from countSubsets(2, 0, 10, arr) and countSubsets(2, 2, 10, arr).
- There are two parameter that change in the recursive solution: i going from 0 to n-1, currentSum going from 0 to target. So we create a 2D array of size (n+1)*(target+1) for memoization.
- We initialize array as -1 to indicate nothing is computed initially.
- Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same subproblems.
// A C++ program to count the number of subsets with a
// sum equal to a target using recursion and memoization
#include <bits/stdc++.h>
using namespace std;
// Function to recursively count subsets with a given sum
// using memoization to avoid redundant calculations
int countSubsets(int i, int currentSum, int target,
vector<int> &arr, vector<vector<int>> &memo) {
// Get the size of the array
int n = arr.size();
// Base case: If we've processed all elements in the array
if (i == n)
// Return 1 if the current subset's
// sum equals the target, else return 0
return (currentSum == target);
// Check if the result for the current state is already computed
if (memo[i][currentSum] != -1)
return memo[i][currentSum];
// Case 1: Exclude the current element and
// move to the next
int exclude = countSubsets(i + 1, currentSum, target, arr, memo);
// Case 2: Include the current element in the subset
int include = 0;
// Only include the current element if
// adding it does not exceed the target sum
if ((arr[i] + currentSum) <= target)
include = countSubsets(i + 1, currentSum + arr[i], target, arr, memo);
// Store the result in the memoization table
// and return it
return memo[i][currentSum] = (include + exclude);
}
// Function to initiate the recursive subset count with memoization
// Parameters:
// - arr: Input array of integers
// - target: Target sum for the subsets
int perfectSum(vector<int> &arr, int target) {
// Get the size of the array
int n = arr.size();
// Initialize a 2D memoization table with -1
// Rows represent indices in the array
// Columns represent possible sums up to the target
vector<vector<int>> memo(n + 1, vector<int>(target + 1, -1));
// Start the recursion from the first element with
// a current sum of 0
return countSubsets(0, 0, target, arr, memo);
}
int main() {
vector<int> arr = {1, 2, 3, 3};
int target = 6;
cout << perfectSum(arr, target);
return 0;
}
// A Java program to count the number of subsets with a
// sum equal to a target using recursion and memoization
import java.util.Arrays;
class GfG {
// Function to recursively count
// subsets with a given sum using memoization
static int countSubsets(int i, int currentSum, int target,
int[] arr, int[][] memo) {
int n = arr.length;
// Base case: If we've processed all elements in the array
if (i == n)
// Return 1 if the current subset's sum
// equals the target, else return 0
return (currentSum == target) ? 1 : 0;
// Check if the result for the current state
// is already computed
if (memo[i][currentSum] != -1)
return memo[i][currentSum];
// Case 1: Exclude the current element
int exclude = countSubsets(i + 1, currentSum, target, arr, memo);
// Case 2: Include the current element
int include = 0;
if (currentSum + arr[i] <= target)
include = countSubsets(i + 1, currentSum + arr[i],
target, arr, memo);
// Store the result in the memoization
// table and return it
memo[i][currentSum] = include + exclude;
return memo[i][currentSum];
}
// Function to initiate the recursive subset count
static int perfectSum(int[] arr, int target) {
int n = arr.length;
// Initialize a 2D memoization table with -1
int[][] memo = new int[n + 1][target + 1];
for (int[] row : memo)
Arrays.fill(row, -1);
return countSubsets(0, 0, target, arr, memo);
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 3};
int target = 6;
System.out.println(perfectSum(arr, target));
}
}
# A Python program to count the number of subsets with a
# sum equal to a target using recursion and memoization
def countSubsets(i, currentSum, target, arr, memo):
n = len(arr)
# Base case: If we've processed all elements
if i == n:
return 1 if currentSum == target else 0
# Check if result is already computed
if memo[i][currentSum] != -1:
return memo[i][currentSum]
# Case 1: Exclude the current element
exclude = countSubsets(i + 1, currentSum, target, arr, memo)
# Case 2: Include the current element
include = 0
if currentSum + arr[i] <= target:
include = countSubsets(i + 1, currentSum + arr[i], target, arr, memo)
# Store result in memoization table and return it
memo[i][currentSum] = include + exclude
return memo[i][currentSum]
def perfectSum(arr, target):
n = len(arr)
# Initialize a 2D memoization table with -1
memo = [[-1 for _ in range(target + 1)] for _ in range(n + 1)]
return countSubsets(0, 0, target, arr, memo)
if __name__ == "__main__":
arr = [1, 2, 3, 3]
target = 6
print(perfectSum(arr, target))
// A C# program to count the number of subsets with a
// sum equal to a target using recursion and memoization
using System;
class GfG {
// Function to recursively count subsets with a
// given sum using memoization
static int CountSubsets(int i, int currentSum,
int target, int[] arr,
int[, ] memo) {
int n = arr.Length;
// Base case: If we've processed all elements
if (i == n)
return (currentSum == target) ? 1 : 0;
// Check if result is already computed
if (memo[i, currentSum] != -1)
return memo[i, currentSum];
// Case 1: Exclude the current element
int exclude = CountSubsets(i + 1, currentSum,
target, arr, memo);
// Case 2: Include the current element
int include = 0;
if (currentSum + arr[i] <= target)
include
= CountSubsets(i + 1, currentSum + arr[i],
target, arr, memo);
// Store result in memoization table and return it
memo[i, currentSum] = include + exclude;
return memo[i, currentSum];
}
// Function to initiate the recursive subset count
static int PerfectSum(int[] arr, int target) {
int n = arr.Length;
// Initialize a 2D memoization table with -1
int[, ] memo = new int[n + 1, target + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= target; j++)
memo[i, j] = -1;
return CountSubsets(0, 0, target, arr, memo);
}
static void Main(string[] args) {
int[] arr = { 1, 2, 3, 3 };
int target = 6;
Console.WriteLine(PerfectSum(arr, target));
}
}
// A Javascript program to count the number of subsets with
// a sum equal to a target using recursion and memoization
function countSubsets(i, currentSum, target, arr, memo) {
const n = arr.length;
// Base case: If we've processed all elements
if (i === n) {
return currentSum === target ? 1 : 0;
}
// Check if result is already computed
if (memo[i][currentSum] !== -1) {
return memo[i][currentSum];
}
// Case 1: Exclude the current element
const exclude = countSubsets(i + 1, currentSum, target,
arr, memo);
// Case 2: Include the current element
let include = 0;
if (currentSum + arr[i] <= target) {
include = countSubsets(i + 1, currentSum + arr[i],
target, arr, memo);
}
// Store result in memoization table and return it
memo[i][currentSum] = include + exclude;
return memo[i][currentSum];
}
function perfectSum(arr, target) {
const n = arr.length;
// Initialize a 2D memoization table with -1
const memo = Array.from(
{length : n + 1}, () => Array(target + 1).fill(-1));
// Start recursion
return countSubsets(0, 0, target, arr, memo);
}
const arr = [ 1, 2, 3, 3 ];
const target = 6;
console.log(perfectSum(arr, target));
Output
3
Using Dynamic Programming (Tabulation) - O(n*target) Time and O(n*target) Space
We create a 2D array dp[n+1][target+1], such that dp[i][j] equals to the number of subsets having sum equal to j from subsets of arr[0...i-1].
We fill the dp array as following:
- We initialize all values of dp[i][j] as 0 and we take dp[0][0]=1 because we take empty subset as our base case.
Iterate over all the values of arr[i] from left to right and for each arr[i], iterate over all the possible values of j i.e. from 1 to target (both inclusive) and fill the dp array as following:
dp[i][j] = dp[i-1][j]
if j>=arr[i-1]
dp[i][j] +=dp[i-1][j-arr[i-1]]
This can be explained as there are only two cases either we take element arr[i] or we don't. We take a element only when it's value is less than or equal to j. Then we look for subsets ending at i-1 such that their sum with arr[i] should be equal to j which is given by dp[i-1][j-arr[i-1]]. The number of subsets from set arr[0..n-1] having sum equal to target will be dp[n][target].
// A C++ program to count the number of subsets with a
// sum equal to a target using tabular dp
#include <bits/stdc++.h>
using namespace std;
int perfectSum(vector<int> &arr, int target) {
// Get the size of the input array
int n = arr.size();
// Create a 2D DP table with dimensions (n+1) x (target+1)
// dp[i][j] represents the number of ways to achieve a sum 'j'
// using the first 'i' elements of the array
vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
// Base case: There's exactly one way to achieve a
// sum of 0 (by selecting no elements)
dp[0][0] = 1;
// Fill the DP table
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
// First, consider excluding the current element
dp[i][j] = dp[i - 1][j];
// Then, consider including the current element
// (if the remaining sum allows it)
if (j >= arr[i - 1]) {
dp[i][j] += dp[i - 1][j - arr[i - 1]];
}
}
}
// Return the number of ways to achieve the
// target sum using all elements in the array
return dp[n][target];
}
int main() {
vector<int> arr = {1, 2, 3, 3};
int target = 6;
cout << perfectSum(arr, target);
return 0;
}
// A Java program to count the number of subsets with a
// sum equal to a target using tabular dp
import java.util.Arrays;
class GfG {
// Function to count the number of subsets
// with a sum equal to the target using tabular DP
static int perfectSum(int[] arr, int target) {
int n = arr.length;
// Create a 2D DP table
int[][] dp = new int[n + 1][target + 1];
// Base case: There's one way to achieve a
// sum of 0 (by selecting no elements)
dp[0][0] = 1;
// Fill the DP table
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
// Exclude the current element
dp[i][j] = dp[i - 1][j];
// Include the current element if
// it doesn't exceed the current sum
if (j >= arr[i - 1]) {
dp[i][j] += dp[i - 1][j - arr[i - 1]];
}
}
}
// Return the number of ways to achieve the target
// sum
return dp[n][target];
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 3 };
int target = 6;
System.out.println(perfectSum(arr, target));
}
}
# A Python program to count the number of subsets with a
# sum equal to a target using tabular dp
def perfectSum(arr, target):
n = len(arr)
# Create a 2D DP table
dp = [[0] * (target + 1) for _ in range(n + 1)]
# Base case: There's one way to achieve
# a sum of 0 (by selecting no elements)
dp[0][0] = 1
# Fill the DP table
for i in range(1, n + 1):
for j in range(target + 1):
# Exclude the current element
dp[i][j] = dp[i - 1][j]
# Include the current element
# if it doesn't exceed the current sum
if j >= arr[i - 1]:
dp[i][j] += dp[i - 1][j - arr[i - 1]]
# Return the number of ways to achieve
# the target sum
return dp[n][target]
if __name__ == "__main__":
arr = [1, 2, 3, 3]
target = 6
print(perfectSum(arr, target))
// A C# program to count the number of subsets with a
// sum equal to a target using tabular dp
using System;
class GfG {
// Function to count the number of subsets
// with a sum equal to the target using tabular DP
static int perfectSum(int[] arr, int target) {
int n = arr.Length;
// Create a 2D DP table
int[, ] dp = new int[n + 1, target + 1];
// Base case: There's one way to
// achieve a sum of 0 (by selecting no elements)
dp[0, 0] = 1;
// Fill the DP table
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
// Exclude the current element
dp[i, j] = dp[i - 1, j];
// Include the current element
// if it doesn't exceed the current sum
if (j >= arr[i - 1]) {
dp[i, j] += dp[i - 1, j - arr[i - 1]];
}
}
}
// Return the number of ways to achieve the target
// sum
return dp[n, target];
}
static void Main(string[] args) {
int[] arr = { 1, 2, 3, 3 };
int target = 6;
Console.WriteLine(perfectSum(arr, target));
}
}
// A Javascript program to count the number of subsets with
// a sum equal to a target using tabular dp
function perfectSum(arr, target) {
const n = arr.length;
// Create a 2D DP table
const dp = Array.from({length : n + 1},
() => Array(target + 1).fill(0));
// Base case: There's one way to achieve
// a sum of 0 (by selecting no elements)
dp[0][0] = 1;
// Fill the DP table
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= target; j++) {
// Exclude the current element
dp[i][j] = dp[i - 1][j];
// Include the current element if it doesn't
// exceed the current sum
if (j >= arr[i - 1]) {
dp[i][j] += dp[i - 1][j - arr[i - 1]];
}
}
}
// Return the number of ways to achieve
// the target sum
return dp[n][target];
}
const arr = [ 1, 2, 3, 3 ];
const target = 6;
console.log(perfectSum(arr, target));
Output
3
Using Space Optimised DP - O(n*target) Time and O(target) Space
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a two 1D array of size target+1 namely prev and curr to store the computations. The final answer is equal to curr[target].
// A C++ program to count the number of subsets with a
// sum equal to a target using space-optimized tabular DP
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the number of subsets with a given sum
// Parameters:
// - arr: Input array of integers
// - target: Target sum for the subsets
int perfectSum(vector<int> &arr, int target) {
int n = arr.size();
// Create two 1D DP arrays: `prev` for the previous state
// and `curr` for the current state
vector<int> prev(target + 1, 0), curr(target + 1, 0);
// Base case: There's one way to achieve a sum
// of 0 (by selecting no elements)
prev[0] = 1;
// Iterate through the elements of the array
for (int i = 1; i <= n; i++) {
// Start by copying the previous state
// to the current state
curr = prev;
// Update the current DP array for sums up to the target
for (int j = 0; j <= target; j++) {
// If the current element can be included in the subset
if (j >= arr[i - 1]) {
curr[j] += prev[j - arr[i - 1]];
}
}
// Move to the next state by updating
// `prev` to `curr`
prev = curr;
}
// Return the number of ways to
// achieve the target sum
return curr[target];
}
int main() {
vector<int> arr = {1, 2, 3, 3};
int target = 6;
cout << perfectSum(arr, target);
return 0;
}
// A Java program to count the number of subsets with a
// sum equal to a target using space-optimized tabular DP
import java.util.*;
class GfG {
// Function to calculate the number of subsets with a
// given sum
static int perfectSum(int[] arr, int target) {
int n = arr.length;
// Create two 1D DP arrays: `prev` for the previous
// state and `curr` for the current state
int[] prev = new int[target + 1];
int[] curr = new int[target + 1];
// Base case: There's one way to achieve a sum
// of 0 (by selecting no elements)
prev[0] = 1;
// Iterate through the elements of the array
for (int i = 1; i <= n; i++) {
// Start by copying the previous state
// to the current state
System.arraycopy(prev, 0, curr, 0, target + 1);
// Update the current DP array for sums up to
// the target
for (int j = 0; j <= target; j++) {
// If the current element can be included in
// the subset
if (j >= arr[i - 1]) {
curr[j] += prev[j - arr[i - 1]];
}
}
// Move to the next state by updating `prev` to
// `curr`
System.arraycopy(curr, 0, prev, 0, target + 1);
}
// Return the number of ways to achieve the target
// sum
return curr[target];
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 3 };
int target = 6;
System.out.println(perfectSum(arr, target));
}
}
# A Python program to count the number of subsets with a
# sum equal to a target using space-optimized tabular DP
def perfectSum(arr, target):
n = len(arr)
# Create two 1D DP arrays: `prev` for the previous state
# and `curr` for the current state
prev = [0] * (target + 1)
curr = [0] * (target + 1)
# Base case: There's one way to achieve a sum
# of 0 (by selecting no elements)
prev[0] = 1
# Iterate through the elements of the array
for i in range(1, n + 1):
# Start by copying the previous state
# to the current state
curr = prev[:]
# Update the current DP array for sums up
# to the target
for j in range(target + 1):
# If the current element can be included
# in the subset
if j >= arr[i - 1]:
curr[j] += prev[j - arr[i - 1]]
# Move to the next state by updating `prev` to `curr`
prev = curr[:]
# Return the number of ways to achieve the target sum
return curr[target]
arr = [1, 2, 3, 3]
target = 6
print(perfectSum(arr, target))
// A C# program to count the number of subsets with a
// sum equal to a target using space-optimized tabular DP
using System;
class GfG {
// Function to calculate the number of subsets with a
// given sum
static int perfectSum(int[] arr, int target) {
int n = arr.Length;
// Create two 1D DP arrays: `prev` for the previous
// state and `curr` for the current state
int[] prev = new int[target + 1];
int[] curr = new int[target + 1];
// Base case: There's one way to achieve a sum
// of 0 (by selecting no elements)
prev[0] = 1;
// Iterate through the elements of the array
for (int i = 1; i <= n; i++) {
// Start by copying the previous state
// to the current state
Array.Copy(prev, curr, target + 1);
// Update the current DP array for sums up to
// the target
for (int j = 0; j <= target; j++) {
// If the current element can be included in
// the subset
if (j >= arr[i - 1]) {
curr[j] += prev[j - arr[i - 1]];
}
}
// Move to the next state by updating `prev` to
// `curr`
Array.Copy(curr, prev, target + 1);
}
// Return the number of ways to achieve the target
// sum
return curr[target];
}
static void Main(string[] args) {
int[] arr = { 1, 2, 3, 3 };
int target = 6;
Console.WriteLine(perfectSum(arr, target));
}
}
// A Javascript program to count the number of subsets with
// a sum equal to a target using space-optimized tabular DP
function perfectSum(arr, target) {
let n = arr.length;
// Create two 1D DP arrays: `prev` for the previous
// state and `curr` for the current state
let prev = new Array(target + 1).fill(0);
let curr = new Array(target + 1).fill(0);
// Base case: There's one way to achieve a sum
// of 0 (by selecting no elements)
prev[0] = 1;
// Iterate through the elements of the array
for (let i = 1; i <= n; i++) {
// Start by copying the previous state
// to the current state
curr = [...prev ];
// Update the current DP array for sums up to the
// target
for (let j = 0; j <= target; j++) {
// If the current element can be included in the
// subset
if (j >= arr[i - 1]) {
curr[j] += prev[j - arr[i - 1]];
}
}
// Move to the next state by updating `prev` to
// `curr`
prev = [...curr ];
}
// Return the number of ways to achieve
// the target sum
return curr[target];
}
const arr = [ 1, 2, 3, 3 ];
const target = 6;
console.log(perfectSum(arr, target));
Output
3