DP #05. Subset Sum Partition Problem. - mbhushan/dynpro GitHub Wiki
(5). Subset Sum / Partition Problem.
Given an array of non negative numbers and a total, is there subset of numbers in this
array which adds up to given total. Another variation is given an array is it possible
to split it up into 2 equal sum partitions. Partition need not be equal sized. Just
equal sum.
Input:
int [] A = {2, 3, 7, 8, 10}
int target = 11
Formula:
if (A[i] <= j) {
T[i][j] = T[i-1][j-A[i]] || T[i-1][j]
} else {
T[i][j] = T[i-1][j]
}
Time complexity - O(input.size * total_sum)
Space complexity - O(input.size * total_sum)
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 2 |
T |
F |
T |
F |
F |
F |
F |
F |
F |
F |
F |
F |
| 3 |
T |
F |
T |
T |
F |
T |
F |
F |
F |
F |
F |
F |
| 7 |
T |
F |
T |
T |
F |
T |
F |
T |
F |
T |
T |
F |
| 8 |
T |
F |
T |
T |
F |
T |
F |
T |
T |
F |
T |
T |
| 10 |
T |
F |
T |
T |
F |
T |
F |
T |
T |
F |
T |
T |
Subset Sum