SUBSET SUM PROBLEM
TEST TIME ON THE
URL:
SUBSET SUM PROBLEM
EXPLANATION
The Subset Sum Problem is a classic optimization problem in computer
science and mathematics. Given a set of positive integers and a
target sum, the goal is to determine whether there exists a subset of
the given set whose elements add up to the target sum.
SUBSET SUM PROBLEM
EXAMPLE
Input: values[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.
SUBSET SUM PROBLEM
EXAMPLE
Input: values[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.
SUBSET SUM PROBLEM
APPROACHES
1. Recursive Solution
2. Dynamic Programming Top Down Solution-algorithm
SUBSET SUM PROBLEM
RECURSIVE SOLUTION
The Recursive Approach involves solving a problem by breaking it
into smaller subproblems of the same type.
In each step, the function calls itself with reduced input, and the
results of subproblems are combined to obtain the final solution.
This approach often leads to concise and elegant code but may
suffer from efficiency issues, such as redundant computations.
SUBSET SUM PROBLEM
RECURSIVE SOLUTION
[value]
/ \
value > targetSum value <= targetSumional space reserved. Only
Stack space is used in recursion.
SUBSET SUM PROBLEM
RECURSIVE SOLUTION
if value > targetSum; We can’t include this item in the subset. We don’t have
a choice
if value <= targetSum; We have a choice to either include this item in the
subset or don’t. Whichever choice leads us to the target sum will be chosen.
SUBSET SUM PROBLEM
RECURSIVE SOLUTION
Recursive structure
For every item, we have two choices - either include this item in the subset or don’t.
We will consider both the choices and determine if we can find a subset of sum S using
any of the choices or not.
There will be a subset of sum S using values from index 1..n if
we can find a subset of sum S using values from index 1..n-1 (Excluding the nth item)
or
we can find a subset of sum S-values[i] using values from index 1..n-1 (Including the
nth item)
SUBSET SUM PROBLEM
RECURSIVE SOLUTION
If the value of the nth item is greater than the target sum S then we can’t
include this item in the subset and choice 1 is the only possibility. Let’s
write our recursive structure mathematically:
SubsetSum(S, n) = SubsetSum(S, n-1); if values[n] > S
SubsetSum(S, n) = SubsetSum(S, n-1) || SubsetSum(S - values[n], n-1); if
values[n] <= S
SUBSET SUM PROBLEM
RECURSIVE SOLUTION
Base condition
To identify the base condition of recursion, think about the smallest valid
input (Empty value array or Zero-sum)
SubsetSum(S, 0) = false; for S > 0 // We can't obtain a positive sum with no
items
SubSetSum(0, n) = true; for any value of n // We can obtain a zero sum by not
choosing any items and having
SUBSET SUM PROBLEM
import java.util.Scanner; public static void main(String[] args) {
public class Main { Scanner keyboard = new
private static boolean hasSubsetSum(int[] Scanner(System.in);
values, int targetSum, int n) { int n = keyboard.nextInt();
if (targetSum == 0) { int[] values = new int[n];
return true; for (int i = 0; i < n; i++) {
} values[i] = keyboard.nextInt();
if (n == 0) { }
return false; int target = keyboard.nextInt();
} keyboard.close();
if (values[n - 1] > targetSum) { System.out.println("Has Subset sum: " +
return hasSubsetSum(values, hasSubsetSum(values, target, n));
targetSum, n - 1); }
} }
return hasSubsetSum(values, targetSum -
values[n - 1], n - 1)
|| hasSubsetSum(values,
targetSum, n - 1);
}
SUBSET SUM PROBLEM
TIME AND SPACE COMPLEXITY
Time Complexity: O(2^n) , Exponential.
Space Complexity: O(1), no additional space reserved. Only Stack space is
used in recursion.
SUBSET SUM PROBLEM
DYNAMIC PROGRAMMING TOP DOWN SOLUTION
Dynamic Programming Top-Down solution for the Subset Sum problem
involves breaking the problem into smaller subproblems and solving
them recursively.
Memorization is employed to store and reuse the solutions to
subproblems, avoiding redundant calculations.
This approach enhances efficiency by avoiding repeated computations
and optimally determines whether a subset with a given sum exists
in a given set of numbers.
SUBSET SUM PROBLEM
DYNAMIC PROGRAMMING TOP DOWN SOLUTION-ALGORITHM
1. Initialization:
Create a 2D array `subsetSumMem` to store memoized results.
Initialize the base cases: if the targetSum is 0, return true; if
n is 0, return false.
Check if the solution for the current subproblem is already
memoized. If yes, return the memoized result.
SUBSET SUM PROBLEM
DYNAMIC PROGRAMMING TOP DOWN SOLUTION-ALGORITHM
2. Recursive Calls:
If the current element's value is greater than the targetSum, set
the memorized result and make a recursive call excluding the current
element.
If the current element's value is less than or equal to the
targetSum, set the memorized result by considering two possibilities:
Include the current element and make a recursive call with
reduced target Sum and n.
Exclude the current element and make a recursive call with the
SUBSET SUM PROBLEM
DYNAMIC PROGRAMMING TOP DOWN SOLUTION-ALGORITHM
3. Return Result:
Return the memoized result for the current subproblem.
4. Main Function:
Read input values for the number of elements `n`, the array of
values, and the target sum.
Initialize the memoization array and call the
`hasSubsetSumMemoized` function.
Print whether there exists a subset with the given sum.
SUBSET SUM PROBLEM
DYNAMIC PROGRAMMING TOP DOWN SOLUTION-PSEUDOCODE
function hasSubsetSumRecur(values, targetSum, n):
if targetSum == 0:
return true
if n == 0:
return false
if subsetSumMem[targetSum][n] is not null:
return subsetSumMem[targetSum][n]
if values[n 1] > targetSum:
subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum,
n 1)
else:
subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum
values[n 1], n 1)|| hasSubsetSumRecur(values, targetSum, n 1)
SUBSET SUM PROBLEM
DYNAMIC PROGRAMMING TOP DOWN SOLUTION-PSEUDOCODE
function hasSubsetSumMemoized(values, targetSum, n):
initialize subsetSumMem array with null values
return hasSubsetSumRecur(values, targetSum, n)
main():
n = read_input()
values = read_input_array()
target = read_input()
initialize subsetSumMem array
print "Has Subset sum: " + hasSubsetSumMemoized(values, target,
n)
SUBSET SUM PROBLEM
import java.util.Scanner;
public class SubsetSumTopDown {
private static Boolean[][] subsetSumMem;
private static boolean hasSubsetSumRecur(int[] values, int targetSum, int n) {
if (targetSum == 0) {
return true;
}
if (n == 0) {
return false;
}
if (subsetSumMem[targetSum][n] != null) {
return subsetSumMem[targetSum][n];
}
if (values[n - 1] > targetSum) {
subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum, n - 1);
} else {
subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum - values[n -
1], n - 1)
|| hasSubsetSumRecur(values, targetSum, n - 1);
}
return subsetSumMem[targetSum][n];
}
SUBSET SUM PROBLEM
private static boolean hasSubsetSumMemoized(int[] values, int targetSum, int n) {
subsetSumMem = new Boolean[targetSum + 1][n + 1];
for (int s = 0; s <= targetSum; s++) {
for (int i = 0; i <= n; i++) {
subsetSumMem[s][i] = null;
}
}
return hasSubsetSumRecur(values, targetSum, n);
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.println("Has Subset sum: " + hasSubsetSumMemoized(values,
target, n));
}
}
SUBSET SUM PROBLEM
TIME AND SPACE COMPLEXITY
Time Complexity:
The time complexity is O(n * targetSum), where n is the number of elements
and targetSum is the target sum. This is due to the nested loops in the
main function and the recursive calls.
Space Complexity:
The space complexity: The space complexity is O(targetSum * n) for the
memoization array.
INTERVIEW QUESTION
1. Explain the Subset Sum problem and its significance.
Answer: Subset Sum involves determining if there exists a subset
of given numbers with a sum equal to a target value. It's vital in
optimization, cryptography, and resource allocation.
INTERVIEW QUESTION
2. How does the dynamic programming approach solve the Subset Sum
problem?
Answer: Dynamic programming optimally solves Subset Sum by
breaking it into subproblems, memoizing results, and efficiently
determining whether a subset with a given sum exists.
INTERVIEW QUESTION
3. Can you briefly describe the difference between the top-down and
bottom-up approaches for Subset Sum?
Answer: The top-down approach uses recursion with memoization,
while the bottom-up approach builds solutions iteratively. Both aim
to optimize by avoiding redundant computations.
INTERVIEW QUESTION
4. Discuss a scenario where the Subset Sum problem is applicable in
real-life problems.
Answer: Subset Sum is relevant in scenarios like financial
portfolio optimization, where the goal is to find a combination of
investments that meet a target return.
/ Ethnus /ethnus /
ethnuscodemith Codemithra code_mithra
ra
https://
learn.codemithra.com
om 095 340
