What kind of problems we can solve by this pattern?

Let's take a look at classic knapsack problem.

Given the weights and profits of ‘N’ items, we are asked to put these items in a knapsack which has a capacity ‘C’. The goal is to get the maximum profit from the items in the knapsack. Each item can only be selected once, as we don’t have multiple quantities of any item.

Let’s take the example of Merry, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:

Items: { Apple, Orange, Banana, Melon }

Weights: { 2, 3, 1, 4 }

Profits: { 4, 5, 3, 7 }

Knapsack capacity: 5

Let’s try to put different combinations of fruits in the knapsack, such that their total weight is not more than 5:

Apple + Orange (total weight 5) => 9 profit

Apple + Banana (total weight 3) => 7 profit

Orange + Banana (total weight 4) => 8 profit

Banana + Melon (total weight 5) => 10 profit

This shows that Banana + Melon is the best combination, as it gives us the maximum profit and the total weight does not exceed the capacity.

Basic Recursive Approach

We either include i or not.

PSEUDOCODE:
for each item 'i' 
  create a new set which INCLUDES item 'i' if the total weight does not exceed the capacity, and 
     recursively process the remaining capacity and items
  create a new set WITHOUT item 'i', and recursively process the remaining items 
return the set from the above two sets with higher profit

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/cd1c60bd-19e0-4d47-95c7-bcba664a0fa1/Untitled.png

public int solveKnapsack(int[] profits, int[] weights, int capacity) {
  return this.knapsackRecursive(profits, weights, capacity, 0);
}

private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
  **// base checks**
  if (capacity <= 0 || currentIndex >= profits.length)
    return 0;

  **// recursive call after choosing the element at the currentIndex
  // if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this**
  int profit1 = 0;
  if( weights[currentIndex] <= capacity )
      profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
              capacity - weights[currentIndex], currentIndex + 1);

  **// recursive call after excluding the element at the currentIndex**
  int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

  return Math.max(profit1, profit2);

Time complexity