Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-02-01

posted Feb 1, 2019, 6:30 AM by Konstantinovich Samuel   [ updated Feb 1, 2019, 7:54 AM ]
Do Now:
No computers until after discussion.

There is an array of integers, and we want to calculate all possible sums
of subgroups of those values.
e.g. [ 1, 5, 2] can make 0, 1,2,5,6,7,3,8

Given an array of ints, is it possible to choose a group of some of the ints,
such that the group sums to the given target?

boolean canMakeSum(ary, targetSum)
    canMakeSum( [1,5,2] , 10) // false
    canMakeSum( [1,5,2] , 6) // true
    canMakeSum( [1,5,2] , 4) // false
    canMakeSum( [1,5,2] , 8) // true

Discussion: (Write in notes)
1. How can we do this recursively? [does not matter tail or not]
What will be the same as yesterday's problem?
What must you change?
You will need to call the recursion more than 1 time
    -Diagram a tree of recursive calls for: canMakeSum( [1,5,2] , 6)
    -Decide how you want to combine the return values of the recursive calls into an answer.




Classwork:


Try now to complete the two main problems:
GroupSum
splitArray
Homework:

Monday - Recursion repo
Wednesday - Complete the codingbat recursion problems you didn't  (4 more after the classwork)
Comments