Q: what about {CB} since we are considering permutations? (for the 2nd example)
A1: live answered
Q: Can you quickly reopen the writing?
A1: live answered
Q: yes!!
Q: thank you :)
Q: Why do we pass in 'soFar' instead of defining it in the function if it is empty?
A1: live answered
Q: in balanced, why donât we have the ability to add the soFar as a parameter?
A1: It is following a slightly different pattern, where you build up the answer via the return value, not through a parameter
Q: Were the autofill suggestions (like when you start typing a function name, it suggests the whole name) disabled during this pset? Can I turn it back on?
A1: Autocomplete should be enabled by default in Qt.
A2: Sometimes Qt gets confused and loses its head. Quit and restart might fix
A3: Also check your settings under Preferences -> Text Editor -> Completion
Q: are we allowed to pass in a variable like sofar in the PSET methods even if the method only currently takes one parameter?
A1: live answered
A2: You should never be changing provided function prototypes, as that would impact our ability to grade your code. That being said, you are always welcome to make use of additional wrapper functions to define new function prototypes that have all the information you need. These wonât be needed on A3, but will definitely become relevant on A4.
Q: how would this function look if we were to return the power set instead of just printing it out?
A1: live answered
A2: You would have to create a wrapper funciton with an additional parameter (data structure) to keep track of all the generated subsets.
Q: what is the value of "rest" ?
A1: rest = input.substr(1), i.e. so remaining characters after removing first
A2: All characters in the string except the first character
Q: Why not just change input instead of setting this new variable rest?
A1: you could do that as well!
A2: For this problem, that would work fine. Both recursive calls use the same value for rest.
In other situations (permute comes to mind), the change you are making is not the same for all recursive calls, so you want to be careful to keep them separate.
Q: so the reason we say it âendsâ is because it didnât call any new functions?
A1: Yes, a specific instance of the function call âendsâ or terminates once it reaches the end of its code block, having finished all spawned recursive calls.
A2: correct, when the function reaches the base case, it no longer calls itself and reaches the end of the function
Q: is this like a depth first search?
A1: Yes!
Q: Wouldnât finding ârestâ on a one character string return an index out of bounds error?
A1: live answered
A2: No, you are allowed to call str.substr(str.length()) without it crashing â it will just return the empty string.
Q: would it be wrong to go down the no paths first?
A1: No, it would explore the same subsets, but would visit them in different order
A2: no
A3: Nope, reversing the order of the two calls in this case is fine.
Q: How did the funciton âback up?â
A1: live answered
Q: Is backtracking only with combinations? Is backtracking in permutations?
A1: Backtracking can be used for both
Q: Is this the general form a recusive function would take for down and back problems (like with the two sequential recursive calls)
A1: live answered
A2: Yes, although you can sometimes have a variable number of recursive calls and/or combined with a for loop as we saw on Monday.
Q: should recursive functions never use for loops?
A1: live answered
A2: For loops can often be useful when writing recursive functions to enumaerate over all possible options you have at a given step!
Q: Could this be implemented with a stack of ints?
A1: Yes
Q: How effective would the algorithm be if you ordered the vector from large to small and started adding to the two sums from the end of the vector (always adding to the smaller one) and using a loop instead of recursion
A1: The number of possible divisions of the Vector is 2^N (this is basically subset problem in disguise). To explore all 2^N options, it requires 2^N, no short cuts âŚ
A2: (although right now, Chris is talking about shortcuts, so just to clarify, stopping at first solution can save us from exploring other options, but in the worst case, e.g. no solution, there is no shortcut to a fully exhaustive serach)
Q: Is there no way to do this question without checking all possible combinations?
A1: live answered
A2: No, this problem requires enumerating differnet combinations to find if an answer exists. It is a âhardâ problem in this way.
Q: It would be more efficient to remove n from the end of the vector and add it back to the end, right?
A1: Correct.
Q: should we add n to the end of the vector because it seems like it will always test the same n
A1: live answered
Q: iâm confused on bool answerâwouldnât we have to add to both in order for them to balance out?
A1: live answered
Q: So the reason we have to unchoose is because if itâs âfalseâ and we make our way back up the tree, we want to make sure the next call (where we do sum2 + n) is checking isPartionable on the same original vector. But canât we just not pass in Vector by reference?
A1: live answered
A2: Yes, that would work also, but would require making a copy of the vector through every call which can be expensive
A3: Yes, correct, as we work our way back up the tree, we have to restore the state of the vector (because its passed by reference). Not passing vector by reference eliminates need for âunchooseâ step but results in many copies of vector being created along the way, which can be inefficient.
Q: Could you show how to improve âint n = rest [0]â (because this one will move the rest down a position)? Does the improvement like âint n = rest [rest.size()-1]â?
A1: live answered
Q: where do the two vectors see if they have the same sum?
A1: In the base case on line 19
A2: Note, this code is not tracking the vector elements, just their sum
Q: What if you wanted to print out the two sets that have the equal sum instead of a boolean?
A1: Coming next!
Q: So the first path explored is where all the numbers are in sum1?
A1: yes
Q: If the sum of the elements in the vector is odd can't you directly return false
A1: No, it is possible for the sum to be odd and still be equal
A2: Ah, I misunderstood what you meant, see followup below
Q: But if the original input vector has elements with sum as odd, there isn't a way to divide it into two right? Of e.g. 1,1,2,3 best case you can have one as 4 and the other as 3 but never as 3.5 and 3.5
A1: Ah, I see what you are saying. We donât know the total sum of all input at first call, but if we did compute total and it were odd, we could conclude there will be no way to divide into two equal subsets.
Q: d
Q: sorry I'm still stuck on this idea. If you keep track of two sums and keep adding the next largest value in the vector to the smaller of the sums then compare the sums at the end. doesn't that also find out if its partionable or not?
A1: Come to office hours after class and we can work through a counter example.
A2: Not necessarily, there are times when doing this may have you miss crucial options. Doing this will keep the sums as close to one another as possible for each iteration but may not find the correct permutation
Q: is vector partitioning an NP-complete problem? [or some variant of NP?]
A1: live answered
A2: Yup.
Q: With bool answer, Iâm confused on the || line
A1: live answered
A2: If either of the conditions evaluates to true we can just return true, because we donât care which option did, otherwise we return false
Q: Could we walk through what that line does with a concrete example?
A1: live answered
Q: but wouldnât this just keep adding elements from the vector to sum1, making sum2 way less?
A1: The very first path that gets executed is the one where elements are only added to sum1 yes, but then it will backtrack and start exploring other options.
Q: How does VectorPair work? Is it a standard C++ structure?
A1: No, its custom defined.