Subset Sum Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/subset-sum

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array of integers A and a target value target. Find whether there exists a subset in the array A where their sum is equal to target.

Naive Approach

This problem can be solved by a brute force recursion. Notice, that when processing a subset, we have 2 choices, either take the current element or don’t take it. So, we can recursively check for the possibilities and return true if we find an appropriate subset, else return false.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1)

Implementation

C++

int checkSum(vector<int> &A, int n, int target) {
	if(target == 0) {
		return 1;
	}
	if(n == 0) {
		return 0;
	}
	if(A[n - 1] > target) {
		return checkSum(A, n - 1, target);
	}
	return checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]);
}
bool hasValidSubset(vector<int>A, int target) {
    return checkSum(A, A.size(), target);
}

Java

class Solution {
	boolean checkSum(int[] A, int n, int target) {
		if(target == 0) {
			return true;
		}
		if(n == 0) {
			return false;
		}
		if(A[n - 1] > target) {
			return checkSum(A, n - 1, target);
		}
		return checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]);
	}
	boolean hasValidSubset(int[] A, int target) {
	    return checkSum(A, A.length, target);
	}
}

Optimal Approach

We can observe that in our naive approach, multiple recursion calls are the same and are being redundantly recalculated. So, we can memoize those recursive calls using Dynamic Programming, to optimize our time complexity. DP[i][j] will represent if it is possible to attain a subset made of the 1st i elements in the array, which adds up to sum j.

Analysis

• Time Complexity: O(n * target)
• Space Complexity: O(n * target)

Implementation

C++

vector<vector<int>> dp;
int checkSum(vector<int> &A, int n, int target) {
	if(target == 0) {
		return 1;
	}
	if(n == 0) {
		return 0;
	}
	if(dp[n][target] != -1){
		return dp[n][target];
	}
	if(A[n - 1] > target) {
		return dp[n][target] = checkSum(A, n - 1, target);
	}
	return dp[n][target] = checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]);
}
bool hasValidSubset(vector<int>A, int target) {
    vector<vector<int>> temp(A.size() + 1, vector<int> (target + 1, -1));
	dp = temp;
    return checkSum(A, A.size(), target);
}

Java

class Solution {
	Boolean dp[][];
	boolean checkSum(int[] A, int n, int target) {
		if(target == 0) {
			return true;
		}
		if(n == 0) {
			return false;
		}
		if(dp[n][target] != null) {
			return dp[n][target];
		}
		if(A[n - 1] > target) {
			dp[n][target] = checkSum(A, n - 1, target);
			return dp[n][target];
		}
		dp[n][target] = (checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]));
		return (dp[n][target]);
	}
	boolean hasValidSubset(int[] A, int target) {
	    dp = new Boolean[A.length + 1][target + 1];
	    return checkSum(A, A.length, target);
	}
}

Bottom-Up Implementation

C++

bool hasValidSubset(vector<int> A, int target) {
	int n = A.size();
	bool dp[n + 1][target + 1];
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= target; j++) {
			if(i == 0 && j != 0) {
				dp[i][j] = false;
			}
			else if(j == 0) {
				dp[i][j] = true;
			}
			else {
				if(j - A[i - 1] >= 0) {
					dp[i][j] = dp[i - 1][j - A[i - 1]] || dp[i - 1][j];
				}
				else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
	}
    return dp[n][target];
}

Java

class Solution {
	boolean hasValidSubset(int[] A, int target) {
		boolean[][] dp = new boolean[A.length + 1][target + 1];
		for(int i = 0; i <= A.length; i++) {
			for(int j = 0; j <= target; j++) {
				if(j == 0) {
					dp[i][j] = true;
				}
				else if(i == 0) {
					dp[i][j] = false;
				}
				else {
					if(j - A[i - 1] >= 0) {
						dp[i][j] = dp[i - 1][j - A[i - 1]] || dp[i - 1][j];
					}
					else {
						dp[i][j] = dp[i - 1][j];
					}
				}
			}
		}
	    return dp[A.length][target];
	}
}