This problem is based on a set. Small subsets of elements of this set are created. The sum of the number of elements of this subset is calculated. This calculated total value is the largest number, smaller than the desired total value. If it is equal to the desired value, it is found. For example,
Let this be our array set.
set[ ] A = { 4, 2 , 10 , 12}
Let our sum value be 20. When we calculate the elements of this set of subsets, none of them is equal to 20. So we need to find the subset with the largest value smaller than that.
sub[ ] = { 12 , 4 , 2 }
When we calculate 12 + 4 + 2 the result will be 18. There is no other subset smaller than 20 and greater than 18.
Before you start writing the code, you should look at the shared algorithm on the "dp_examples" slide. In this algorithm, the base case sum value and array length are 0. In this case 0 must be returned. Another case is that the value of an element in the Array is greater than the sum value. In such a case, the index value of the array should be lowered and recursion should be done. Otherwise, decrease the index number by one, subtract the value of the array from the sum value and put it back into the recurison. Before doing this operation, add the int value resulting from this event with the value of the array in the index and compare the int value with the other recursion to get the maximum int value.
Recursion: Recursion solution can be done using the above algorithm. Base case was determined and returned to 0. The other case was then checked and the Recursion was called again. Finally, the comparison was made and the maximum value was obtained. This maximum value was also returned.
Dynamic Programing: This code should be written according to the algorithm given above. But unlike recursion, Dynamic 2D array is used. The length of this array is "sum x set.lenght". Recursion called recursion in every if case. In Dynamic, this 2D array is either updated or load up.
Memoized Recursion: HashMap is used in this solution. If the values are checked and the controls are used, the algorithm given above is used. However, these if cases are checked from within HashMap. 2 different int values are kept according to if cases. An int value that results from a reduced and recursion invocation of the index. This is called "exclude". Another is the int value, when the maximum is calculated (using the algorithm above). This is called include. HashMap keeps key and value. The key here is "size | sum". Value is the "exclude" and "include" values that we calculated before. Finally, the value in this HashMap is returned.
When we run these solutions, the results are as follows. If the array length is 6 and the sum value is 100, they all calculate in 0 seconds.
When you increase the length and sum value of this array a bit, they will no longer work in 0 seconds. Except for the recursion, the values run again in 0 seconds. The recursion value works for about 1.5 seconds.
When we increase these values a little more, recursion now works much slower. Recursion runs in 7 seconds. Others operate in 1 second again. Recursion gives an "Out Of Memory Error" error when higher values are given.
Higher values must be given to determine whether it is dynamic or Memoized. Because the 2D array is created in the Dynamic algorithm and the length of this array is "sum x set.length", the larger the sum value, the slower Dynamic runs. Array length of 3500 and sum value of 177640 when we do a trial, Dynamic 3 seconds Memoized works in 0 seconds. Thus, the more sum value increases, the more dynamic we have seen.
The complexity of the algorithm written for recursion is as follows.
The total complexity is : T(n) = 3T(n-1) + 1. If the tree is drawn, the process can be solved easily. Since it is called 3 times, the length of the tree has to go down to 3 above k. That's why complexity is O(3^n). The complexity of the algorithm written for Dynamic is shown below.
The total complexity is : T(n) = 3(size x sum) +1 . This complexity also seems to be easy. The complexity is O(size x sum). Memoized's complexity is similar to that of dynamic. The difference between them is the use of maps and checking if cases with them. So the complexity is for Memoized O(size x sum).
