educative.io

Find Selected Elements in Top-Down Approach

Courses
,
#1

Can anyone help?

#2

Since we use recursion, we have to build the list of selected elements as we break down the problem into smaller ones.

For example :

int recursion( int[] nums, int index){
  List<Integer> result = new ArrayList<>();
  if(index == nums.length) 
    return result;

  if( myConditionMet){
    result.add(nums[i]);
    List<Integer> subRes = recursion(nums,  index+1);
    result.addAll(subRes);
  }
  return result;
}

Hope it helps…

#3 
def print_path(dp, lengths, prices, capacity):
  n = len(lengths)
  total_profits = dp[n-1][capacity]
  while n > -1:
    if total_profits != dp[n-1][capacity]:
      total_profits -= prices[n]
      capacity -= lengths[n]
      print(lengths[n], end = " ")
    else:
      n -= 1

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Unbounded Knapsack - Grokking Dynamic Programming Patterns for Coding Interviews