Problem Statement:
Partition A Set Into Two Subsets With Minimum Absolute Sum Difference
Pre-req: Subset Sum equal to target, Recursion on Subsequences
Problem Link: Partition A Set Into Two Subsets With Minimum Absolute Sum Difference
We are given an array ‘ARR’ with N positive integers. We need to partition the array into two subsets such that the absolute difference of the sum of elements of the subsets is minimum.
We need to return only the minimum absolute difference of the sum of elements of the two partitions.
Examples
Example 1:Example 2:
Example 2:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Memorization Approach
Algorithm / Intuition
This question is a slight modification of the problem discussed in the Subset Sum equal to target.
Before discussing the approach for this question, it is important to understand what we did in the previous question of the Subset Sum equal to the target. There we found whether or not a subset exists in an array with a given target sum. We used a dp array to get to our answer.
We used to return dp[n-1][k] as our answer. One interesting thing that is happening is that for calculating our answer for dp[n-1][k], we are also solving multiple sub-problems and at the same time storing them as well. We will use this property to solve the question of this article.
In this question, we need to partition the array into two subsets( say with sum S1 and S2) and we need to return the minimized absolute difference of S1 and S2. But do we need two variables for it? The answer is No. We can use a variable totSum, which stores the sum of all elements of the input array, and then we can simply say S2 = totSum – S1. Therefore we only need one variable S1.
Now, what values can S1 take? Well, it can go anywhere from 0 (no elements in S1) to totSum( all elements in S1). If we observe the last row of the dp array which we had discussed above, it gives us the targets for which there exists a subset. We will set its column value to totSum, to find the answer from 0(smaller limit of S1) to totSum (the larger limit of S1).
Our work is very simple, using the last row of the dp array, we will first find which all S1 values are valid. Using the valid S1 values, we will find S2 (totSum – S1). From this S1 and S2, we will find their absolute difference. We will return the minimum value of this absolute difference as our answer.
From here we will try to find a subsequence in the array with a target as discussed in Subset Sum equal to target after generating the dp array, we will use the last row to find our answer.
Note: Readers are highly advised to watch this video “Recursion on Subsequences” to understand how we generate subsequences using recursion.
Steps to form the recursive solution:
We will first form the recursive solution by the three points mentioned in Dynamic Programming Introduction.
Step 1: Express the problem in terms of indexes.
The array will have an index but there is one more parameter “target”. We are given the initial problem to find whether there exists in the whole array a subsequence whose sum is equal to the target.
So, we can say that initially, we need to find(n-1, target) which means that we need to find whether there exists a subsequence in the array from index 0 to n-1, whose sum is equal to the target. Similarly, we can generalize it for any index ind as follows:
Base Cases:
- If target == 0, it means that we have already found the subsequence from the previous steps, so we can return true.
- If ind==0, it means we are at the first element, so we need to return arr[ind]==target. If the element is equal to the target we return true else false.
Step 2: Try out all possible choices at a given index.
We need to generate all the subsequences. We will use the pick/non-pick technique as discussed in this video “Recursion on Subsequences”.
We have two choices:
- Exclude the current element in the subsequence: We first try to find a subsequence without considering the current index element. For this, we will make a recursive call to f(ind-1,target).
- Include the current element in the subsequence: We will try to find a subsequence by considering the current index as element as part of subsequence. As we have included arr[ind], the updated target which we need to find in the rest if the array will be target – arr[ind]. Therefore, we will call f(ind-1,target-arr[ind]).
Note: We will consider the current element in the subsequence only when the current element is less or equal to the target.
Step 3: Return (taken || notTaken)
As we are looking for only one subset, if any of the one among taken or not taken returns true, we can return true from our function. Therefore, we return ‘or(||)’ of both of them.
The final pseudocode after steps 1, 2, and 3:
Steps to memoize a recursive solution:
If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:
- Create a dp array of size [n][totSum+1]. The size of the input array is ‘n’, so the index will always lie between ‘0’ and ‘n-1’. The target can take any value between ‘0’ and ‘totSum’. Therefore we take the dp array as dp[n][totSum+1]
- We initialize the dp array to -1.
- Whenever we want to find the answer of particular parameters (say f(ind,target)), we first check whether the answer is already calculated using the dp array(i.e dp[ind][target]!= -1 ). If yes, simply return the value from the dp array.
- If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[ind][target] to the solution we get.
- When we get the dp array, we will use its last row to find the absolute minimum difference of two partitions.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to solve the subset sum problem with memoization
bool subsetSumUtil(int ind, int target, vector<int>& arr, vector<vector<int>>& dp) {
// Base case: If the target sum is 0, return true
if (target == 0)
return dp[ind][target] = true;
// Base case: If we have considered all elements and the target is still not 0, return false
if (ind == 0)
return dp[ind][target] = (arr[0] == target);
// If the result for this state is already calculated, return it
if (dp[ind][target] != -1)
return dp[ind][target];
// Recursive cases
// 1. Exclude the current element
bool notTaken = subsetSumUtil(ind - 1, target, arr, dp);
// 2. Include the current element if it doesn't exceed the target
bool taken = false;
if (arr[ind] <= target)
taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp);
// Store the result in the DP table and return
return dp[ind][target] = notTaken || taken;
}
// Function to find the minimum absolute difference between two subset sums
int minSubsetSumDifference(vector<int>& arr, int n) {
int totSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// Initialize a DP table to store the results of the subset sum problem
vector<vector<int>> dp(n, vector<int>(totSum + 1, -1));
// Calculate the subset sum for each possible sum from 0 to the total sum
for (int i = 0; i <= totSum; i++) {
bool dummy = subsetSumUtil(n - 1, i, arr, dp);
}
int mini = 1e9;
for (int i = 0; i <= totSum; i++) {
if (dp[n - 1][i] == true) {
int diff = abs(i - (totSum - i));
mini = min(mini, diff);
}
}
return mini;
}
int main() {
vector<int> arr = {1, 2, 3, 4};
int n = arr.size();
cout << "The minimum absolute difference is: " << minSubsetSumDifference(arr, n);
return 0;
}
import java.util.*;
public class Main {
// Helper function to calculate the minimum absolute difference of two subsets
static int minSubsetSumDifference(ArrayList<Integer> arr, int n) {
int totSum = 0;
// Calculate the total sum of the array elements
for (int i = 0; i < n; i++) {
totSum += arr.get(i);
}
// Create a DP table to store subset sum information
boolean[][] dp = new boolean[n][totSum + 1];
// Initialize the DP table for the first row
for (int i = 0; i <= totSum; i++) {
dp[0][i] = (i == arr.get(0));
}
// Fill in the DP table using bottom-up dynamic programming
for (int ind = 1; ind < n; ind++) {
for (int target = 0; target <= totSum; target++) {
// Calculate if the current element is not taken
boolean notTaken = dp[ind - 1][target];
// Calculate if the current element is taken
boolean taken = false;
if (arr.get(ind) <= target) {
taken = dp[ind - 1][target - arr.get(ind)];
}
// Update the DP table for the current element and target sum
dp[ind][target] = notTaken || taken;
}
}
int mini = Integer.MAX_VALUE;
// Find the minimum absolute difference between two subsets
for (int i = 0; i <= totSum; i++) {
if (dp[n - 1][i]) {
int diff = Math.abs(i - (totSum - i));
mini = Math.min(mini, diff);
}
}
return mini;
}
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
int n = arr.size();
// Calculate and print the minimum absolute difference
System.out.println("The minimum absolute difference is: " + minSubsetSumDifference(arr, n));
}
}
def subsetSumUtil(ind, target, arr, dp):
# Base case: If the target sum is 0, we have found a subset that sums to the target.
if target == 0:
return True
# Base case: If we have reached the first element of the array, check if it equals the target.
if ind == 0:
return arr[0] == target
# Check if the result for this combination of 'ind' and 'target' has already been computed.
if dp[ind][target] != -1:
return dp[ind][target]
# Recursive cases:
# 1. Try not taking the current element.
notTaken = subsetSumUtil(ind - 1, target, arr, dp)
# 2. Try taking the current element if it is less than or equal to the target.
taken = False
if arr[ind] <= target:
taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp)
# Update the DP table and return the result.
dp[ind][target] = notTaken or taken
return dp[ind][target]
def minSubsetSumDifference(arr):
n = len(arr)
totSum = sum(arr)
# Initialize a DP table to store the subset sum information.
dp = [[-1 for i in range(totSum + 1)] for j in range(n)]
# Calculate dummy values for all possible sums using subsetSumUtil.
for i in range(totSum + 1):
dummy = subsetSumUtil(n - 1, i, arr, dp)
# Initialize a variable to track the minimum absolute difference.
mini = int(1e9)
# Iterate through all possible sums.
for i in range(totSum + 1):
if dp[n - 1][i] == True:
# Calculate the difference between the current sum and the complement sum.
diff = abs(i - (totSum - i))
mini = min(mini, diff)
return mini
def main():
arr = [1, 2, 3, 4]
print("The minimum absolute difference is:", minSubsetSumDifference(arr))
if __name__ == "__main__":
main()
function subsetSumUtil(ind, target, arr, dp) {
if (target === 0)
return dp[ind][target] = true;
if (ind === 0)
return dp[ind][target] = arr[0] === target;
if (dp[ind][target] !== -1)
return dp[ind][target];
const notTaken = subsetSumUtil(ind - 1, target, arr, dp);
let taken = false;
if (arr[ind] <= target)
taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp);
return dp[ind][target] = notTaken || taken;
}
// Function to find the minimum absolute difference of two subset sums
function minSubsetSumDifference(arr, n) {
let totSum = 0;
for (let i = 0; i < n; i++) {
totSum += arr[i];
}
// Create a 2D array for dynamic programming
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(totSum + 1).fill(-1);
}
// Calculate the subset sum for all possible sums up to totSum
for (let i = 0; i <= totSum; i++) {
const dummy = subsetSumUtil(n - 1, i, arr, dp);
}
let mini = 1e9;
for (let i = 0; i <= totSum; i++) {
if (dp[n - 1][i] === true) {
const diff = Math.abs(i - (totSum - i));
mini = Math.min(mini, diff);
}
}
return mini;
}
// Main function
function main() {
const arr = [1, 2, 3, 4];
const n = arr.length;
console.log("The minimum absolute difference is: " + minSubsetSumDifference(arr, n));
}
// Run the main function
main();
Output: The minimum absolute difference is: 0
Complexity Analysis
Time Complexity: O(N*totSum) +O(N) +O(N)
Reason: There are two nested loops that account for O(N*totSum), at starting we are running a for loop to calculate totSum and at last a for loop to traverse the last row.
Space Complexity: O(N*totSum) + O(N)
Reason: We are using an external array of size ‘N * totSum’ and a stack space of O(N).
Tabulation Approach
Algorithm / Intuition
To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can set its type as bool and initialize it as false.
First, we need to initialize the base conditions of the recursive solution.
- If target == 0, ind can take any value from 0 to n-1, therefore we need to set the value of the first column as true.
- The first row dp[0][] indicates that only the first element of the array is considered, therefore for the target value equal to arr[0], only cell with that target will be true, so explicitly set dp[0][arr[0]] =true, (dp[0][arr[0]] means that we are considering the first element of the array with the target equal to the first element itself). Please note that it can happen that arr[0]>target, so we first check it: if(arr[0]<=target) then set dp[0][arr[0]] = true.
- After that, we will set our nested for loops to traverse the dp array, and following the logic discussed in the recursive approach, we will set the value of each cell. Instead of recursive calls, we will use the dp array itself.
- When we get the dp array, we will use its last row to find the absolute minimum difference between two partitions.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum absolute difference between two subset sums
int minSubsetSumDifference(vector<int>& arr, int n) {
int totSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// Initialize a DP table to store the results of the subset sum problem
vector<vector<bool>> dp(n, vector<bool>(totSum + 1, false));
// Base case: If no elements are selected (sum is 0), it's a valid subset
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize the first row based on the first element of the array
if (arr[0] <= totSum)
dp[0][totSum] = true;
// Fill in the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
for (int target = 1; target <= totSum; target++) {
// Exclude the current element
bool notTaken = dp[ind - 1][target];
// Include the current element if it doesn't exceed the target
bool taken = false;
if (arr[ind] <= target)
taken = dp[ind - 1][target - arr[ind]];
dp[ind][target] = notTaken || taken;
}
}
int mini = 1e9;
for (int i = 0; i <= totSum; i++) {
if (dp[n - 1][i] == true) {
// Calculate the absolute difference between two subset sums
int diff = abs(i - (totSum - i));
mini = min(mini, diff);
}
}
return mini;
}
int main() {
vector<int> arr = {1, 2, 3, 4};
int n = arr.size();
cout << "The minimum absolute difference is: " << minSubsetSumDifference(arr, n);
return 0;
}
import java.util.*;
public class Main {
// Function to calculate the minimum absolute difference of two subsets
static int minSubsetSumDifference(ArrayList<Integer> arr, int n) {
int totSum = 0;
// Calculate the total sum of the array elements
for (int i = 0; i < n; i++) {
totSum += arr.get(i);
}
// Create a DP table to store subset sum information
boolean[][] dp = new boolean[n][totSum + 1];
// Initialize the DP table for the first row
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize the DP table for the first column
if (arr.get(0) <= totSum) {
dp[0][totSum] = true;
}
// Fill in the DP table using bottom-up dynamic programming
for (int ind = 1; ind < n; ind++) {
for (int target = 1; target <= totSum; target++) {
// Calculate if the current element is not taken
boolean notTaken = dp[ind - 1][target];
// Calculate if the current element is taken
boolean taken = false;
if (arr.get(ind) <= target) {
taken = dp[ind - 1][target - arr.get(ind)];
}
// Update the DP table for the current element and target sum
dp[ind][target] = notTaken || taken;
}
}
int mini = Integer.MAX_VALUE;
// Find the minimum absolute difference between two subsets
for (int i = 0; i <= totSum; i++) {
if (dp[n - 1][i]) {
int diff = Math.abs(i - (totSum - i));
mini = Math.min(mini, diff);
}
}
return mini;
}
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
int n = arr.size();
// Calculate and print the minimum absolute difference
System.out.println("The minimum absolute difference is: " + minSubsetSumDifference(arr, n));
}
}
def minSubsetSumDifference(arr, n):
# Calculate the total sum of the array elements.
totSum = sum(arr)
# Initialize a DP table to store subset sum information.
dp = [[False for i in range(totSum + 1)] for j in range(n)]
# Initialize the base cases for the DP table.
for i in range(n):
dp[i][0] = True
# Handle the base case for the first element in the array.
if arr[0] <= totSum:
dp[0][arr[0]] = True
# Fill in the DP table using dynamic programming.
for ind in range(1, n):
for target in range(1, totSum + 1):
# If the current element is not taken, the result is the same as the previous row.
notTaken = dp[ind - 1][target]
# If the current element is taken, subtract its value from the target and check the previous row.
taken = False
if arr[ind] <= target:
taken = dp[ind - 1][target - arr[ind]]
# Update the DP table with the result of taking or not taking the current element.
dp[ind][target] = notTaken or taken
# Initialize a variable to track the minimum absolute difference.
mini = int(1e9)
# Iterate through all possible sums.
for i in range(totSum + 1):
if dp[n - 1][i] == True:
# Calculate the difference between the current sum and the complement sum.
diff = abs(i - (totSum - i))
mini = min(mini, diff)
return mini
def main():
arr = [1, 2, 3, 4]
n = len(arr)
# Find and print the minimum absolute difference between two subsets.
print("The minimum absolute difference is:", minSubsetSumDifference(arr, n))
if __name__ == '__main__':
main()
function minSubsetSumDifference(arr, n) {
let totSum = 0;
// Calculate the total sum of elements in the array
for (let i = 0; i < n; i++) {
totSum += arr[i];
}
// Create a 2D boolean array for dynamic programming
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(totSum + 1).fill(false);
}
// Initialize the first row of the dp array
for (let i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize the first column of the dp array
if (arr[0] <= totSum) {
dp[0][arr[0]] = true;
}
// Fill the dp array using bottom-up dynamic programming
for (let ind = 1; ind < n; ind++) {
for (let target = 1; target <= totSum; target++) {
const notTaken = dp[ind - 1][target];
let taken = false;
if (arr[ind] <= target) {
taken = dp[ind - 1][target - arr[ind]];
}
dp[ind][target] = notTaken || taken;
}
}
let mini = 1e9;
for (let i = 0; i <= totSum; i++) {
if (dp[n - 1][i] === true) {
const diff = Math.abs(i - (totSum - i));
mini = Math.min(mini, diff);
}
}
return mini;
}
// Main function
function main() {
const arr = [1, 2, 3, 4];
const n = arr.length;
console.log("The minimum absolute difference is: " + minSubsetSumDifference(arr, n));
}
// Run the main function
main();
Output: The minimum absolute difference is: 0
Complexity Analysis
Time Complexity: O(N*totSum) +O(N) +O(N)
Reason: There are two nested loops that account for O(N*totSum), at starting we are running a for loop to calculate totSum, and at last a for loop to traverse the last row.
Space Complexity: O(N*totSum)
Reason: We are using an external array of size ‘N * totSum’. Stack Space is eliminated.
Space Optimization Approach
Algorithm / Intuition
If we closely look the relation,
dp[ind][target] = dp[ind-1][target] || dp[ind-1][target-arr[ind]]
We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.
Note: Whenever we create a new row ( say cur), we need to explicitly set its first element is true according to our base condition.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum absolute difference between two subset sums
int minSubsetSumDifference(vector<int>& arr, int n) {
int totSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// Initialize a boolean vector 'prev' to represent the previous row of the DP table
vector<bool> prev(totSum + 1, false);
// Base case: If no elements are selected (sum is 0), it's a valid subset
prev[0] = true;
// Initialize the first row based on the first element of the array
if (arr[0] <= totSum)
prev[arr[0]] = true;
// Fill in the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
// Create a boolean vector 'cur' to represent the current row of the DP table
vector<bool> cur(totSum + 1, false);
cur[0] = true;
for (int target = 1; target <= totSum; target++) {
// Exclude the current element
bool notTaken = prev[target];
// Include the current element if it doesn't exceed the target
bool taken = false;
if (arr[ind] <= target)
taken = prev[target - arr[ind]];
cur[target] = notTaken || taken;
}
// Set 'cur' as the 'prev' for the next iteration
prev = cur;
}
int mini = 1e9;
for (int i = 0; i <= totSum; i++) {
if (prev[i] == true) {
// Calculate the absolute difference between two subset sums
int diff = abs(i - (totSum - i));
mini = min(mini, diff);
}
}
return mini;
}
int main() {
vector<int> arr = {1, 2, 3, 4};
int n = arr.size();
cout << "The minimum absolute difference is: " << minSubsetSumDifference(arr, n);
return 0;
}
import java.util.*;
public class Main {
// Function to calculate the minimum absolute difference of two subsets
static int minSubsetSumDifference(ArrayList<Integer> arr, int n) {
int totSum = 0;
// Calculate the total sum of the array elements
for (int i = 0; i < n; i++) {
totSum += arr.get(i);
}
// Create an array to store DP results for the previous row
boolean[] prev = new boolean[totSum + 1];
// Initialize the DP array for the first row
prev[0] = true;
// Initialize the DP array for the first column
if (arr.get(0) <= totSum) {
prev[arr.get(0)] = true;
}
// Fill in the DP array using bottom-up dynamic programming
for (int ind = 1; ind < n; ind++) {
// Create an array to store DP results for the current row
boolean[] cur = new boolean[totSum + 1];
cur[0] = true;
for (int target = 1; target <= totSum; target++) {
// Calculate if the current element is not taken
boolean notTaken = prev[target];
// Calculate if the current element is taken
boolean taken = false;
if (arr.get(ind) <= target) {
taken = prev[target - arr.get(ind)];
}
// Update the DP array for the current element and target sum
cur[target] = notTaken || taken;
}
prev = cur;
}
int mini = Integer.MAX_VALUE;
// Find the minimum absolute difference between two subsets
for (int i = 0; i <= totSum; i++) {
if (prev[i]) {
int diff = Math.abs(i - (totSum - i));
mini = Math.min(mini, diff);
}
}
return mini;
}
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
int n = arr.size();
// Calculate and print the minimum absolute difference
System.out.println("The minimum absolute difference is: " + minSubsetSumDifference(arr, n));
}
}
def minSubsetSumDifference(arr, n):
# Calculate the total sum of the array elements.
totSum = sum(arr)
# Initialize a boolean array 'prev' to store the results for the previous row.
prev = [False] * (totSum + 1)
prev[0] = True # Base case: An empty subset can always achieve a sum of 0.
# Handle the base case for the first element in the array.
if arr[0] <= totSum:
prev[arr[0]] = True
# Iterate through the elements in the array.
for ind in range(1, n):
# Initialize a new boolean array 'cur' for the current row.
cur = [False] * (totSum + 1)
cur[0] = True # An empty subset can always achieve a sum of 0.
# Fill in the 'cur' array using dynamic programming.
for target in range(1, totSum + 1):
# If the current element is not taken, the result is the same as the previous row.
notTaken = prev[target]
# If the current element is taken, subtract its value from the target and check the previous row.
taken = prev[target - arr[ind]] if arr[ind] <= target else False
# Update the 'cur' array with the result of taking or not taking the current element.
cur[target] = notTaken or taken
# Update 'prev' to 'cur' for the next iteration.
prev = cur
# Initialize a variable to track the minimum absolute difference.
mini = int(1e9)
# Iterate through all possible sums.
for i in range(totSum + 1):
if prev[i]:
# Calculate the difference between the current sum and the complement sum.
diff = abs(i - (totSum - i))
mini = min(mini, diff)
return mini
def main():
arr = [1, 2, 3, 4]
n = len(arr)
# Find and print the minimum absolute difference between two subsets.
print("The minimum absolute difference is:", minSubsetSumDifference(arr, n))
if __name__ == "__main__":
main()
function minSubsetSumDifference(arr, n) {
let totSum = 0;
// Calculate the total sum of elements in the array
for (let i = 0; i < n; i++) {
totSum += arr[i];
}
// Initialize the previous array for dynamic programming
const prev = new Array(totSum + 1).fill(false);
prev[0] = true;
// Initialize the first column of the dp array
if (arr[0] <= totSum) {
prev[arr[0]] = true;
}
// Fill the dp array using bottom-up dynamic programming
for (let ind = 1; ind < n; ind++) {
const cur = new Array(totSum + 1).fill(false);
cur[0] = true;
for (let target = 1; target <= totSum; target++) {
const notTaken = prev[target];
let taken = false;
if (arr[ind] <= target) {
taken = prev[target - arr[ind]];
}
cur[target] = notTaken || taken;
}
// Update 'prev' array with 'cur' for the next iteration
for (let i = 0; i < prev.length; i++) {
prev[i] = cur[i];
}
}
let mini = 1e9;
for (let i = 0; i <= totSum; i++) {
if (prev[i] === true) {
const diff = Math.abs(i - (totSum - i));
mini = Math.min(mini, diff);
}
}
return mini;
}
// Main function
function main() {
const arr = [1, 2, 3, 4];
const n = arr.length;
console.log("The minimum absolute difference is: " + minSubsetSumDifference(arr, n));
}
// Run the main function
main();
Output:The minimum absolute difference is: 0
Complexity Analysis
Time Complexity: O(N*totSum) +O(N) +O(N)
Reason: There are two nested loops that account for O(N*totSum), at starting we are running a for loop to calculate totSum and at last a for loop to traverse the last row.
Space Complexity: O(totSum)
Reason: We are using an external array of size ‘totSum+1’ to store only one row.
Video Explanation
Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article