Backtracking vs Dynamic Programming

Table of Contents

1. Introduction
2. Similar Brute-force Solution
3. Understand the Concepts
4. Similarities and Differences

1. Introduction

Let’s begin by examining the two coding questions below.

Q1: Combination Sum

Reference: Q1 is from LeetCode. For more details please refer to the link.

Q2: 0/1 Knapsack

Reference: Q2 is from GeeksforGeeks. For more details please refer to the link.

When I first encountered these two questions, they seemed similar to me, as both required searching for combinations under certain constraints. Initially, I solved them using similar brute-force approaches. However, I later discovered that Q1 is a classic backtracking problem, while Q2 is a classic dynamic programming problem. This distinction motivated me to explore their similarities and differences.

2. Similar Brute-force Solution

Q1: Combination Sum — brute-force solution

Let’s break down the problem using a brute-force approach,

• Step 1: Find a combination
• Step 2: Compute its sum
• Step 3: Save the combination if the sum equals the target
• Repeat steps 1 to 3 until no more combinations remain

The key challenge is to find all possible combinations while allowing the same number to be chosen multiple times. To further break down the combination search process:

• Find all combinations that include one number
• Find all combinations that include two numbers
• Find all combinations that include three numbers
• … and so on

One intuition is that once we have a combination with n numbers, we can generate combinations with n+1 numbers by adding a single candidate number. Follows with below conditions:

• If the sum of a combination equals the target, save it to the results and stop expanding it further. (green nodes)
• If the sum exceeds the target, discard the combination and stop expanding it further. (red nodes)
• If the sum is less than the target, continue adding numbers to explore more possibilities. (white nodes)

Let’s visualize this solution with a diagram.

It is an n-ary tree, where each node must store essential information:

• Comb. The numbers included in this node’s combination
• Start. The starting index in the candidate list for adding new numbers. This prevents duplicate combinations
• Target. The remaining target value, updated as new numbers are added to the combination

The original problem can be transformed into a tree traversal problem, which can be solved recursively using DFS.

#include <vector>
using namespace std;

class Q1Solution
{
public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
  {
    vector<vector<int>> rlt;
    if (candidates.size() <= 0) return rlt;

    vector<int> comb;
    recurSearch(candidates, comb, 0, target, rlt);
    return rlt;
  }

  void recurSearch(const vector<int>& candidates, std::vector<int>& comb, 
                   int start, int target, vector<vector<int>>& rlt)
  {
    // Base case
    if (target==0) {
      rlt.push_back(comb);
      return;
    }

    for (std::size_t i = start; i < candidates.size(); ++i) {
      if (candidates[i] <= target) {
        comb.push_back(candidates[i]);
        recurSearch(candidates, comb, i, target - candidates[i], rlt);
        comb.pop_back();
      }
      // if (candidates[i] > target) do nothing;
    }
  }
};

Q2: 0/1 Knapsack — Brute-force Solution

Similar to Q1, let’s break down the problem using a brute-force approach,

• Step 1: Find a combination
• Step 2: Compute the total profit of the combination
• Step 3: Update the best combination if the new profit sum is higher
• Repeat steps 1 to 3 until no more combinations remain

The key challenge is to explore all possible combinations while ensuring that each number is selected only once. To further break down the combination search process:

• Find all combinations that include one number
• Find all combinations that include two numbers
• Find all combinations that include three numbers
• … and so on

Similar to Q1, one intuition is that once we have a combination containing n numbers, we can generate new combinations with n+1 numbers by adding a single candidate, following these conditions:

• If the total weight of a combination equals the weight limit, the profit is valid, and no additional numbers can be added due to the weight limit. (green nodes)
• If the total weight exceeds the weight limit, the profit is invalid, and the combination cannot be extended further. (red nodes)
• If the total weight is below the weight limit, the profit is valid, and we should consider adding more numbers to explore further possibilities. (white nodes)

Now, let’s visualize this solution with a diagram.

It is an n-ary tree, where each node must store essential information,

• Comb. The items included in this node’s combination
• Start. The starting index in the candidate list for adding new items. This prevents duplicate combinations
• W. The remaining weight limit, updated as new items added
• Profit. The total profit of the current combination

The original problem can be transformed into a tree traversal problem, which can be solved recursively using DFS.

  class Q2Solution {
  public:
    int solveKnapsack(vector<int> &profits, vector<int> &weights, int capacity) {
      if (profits.empty() || weights.empty() || capacity <= 0) return 0;

      vector<int> comb;
      // The root node must start at -1
      // to ensure that the first child node begins from 0 (start + 1)
      // since each item can only be selected once
      return recurSearch(profits, weights, comb, -1, capacity, 0);
    }

    int recurSearch(const vector<int>& profits, const vector<int>& weights, 
                    vector<int>& comb, int start, int W, const int profit) 
    {
      // Base case
      if (W<0) return 0;

      int max_profit = profit;
      for (int i=start+1; i<profits.size(); ++i) {
        comb.push_back(weights[i]);
        int child_profit = recurSearch(profits, weights, comb, i, 
                                       W - weights[i], profit + profits[i]);
        max_profit = std::max(max_profit, child_profit);
        comb.pop_back();
      }

      return max_profit;
    }
  };

3. Understand the Concepts

What is backtracking?

Let’s take a closer look at the code inside the for loop.

Q1: Combination Sum

comb.push_back(candidates[i]);
recurSearch(candidates, comb, i, target - candidates[i], rlt);
comb.pop_back();

Q2: 0/1 Knapsack

comb.push_back(weights[i]);
max_profit = std::max(max_profit, recurSearch(profits, weights, comb, i, W - weights[i], profit + profits[i]));
comb.pop_back();

A new item is added to the current combination, and the function is then called recursively with the updated combination. Once the recursive call completes, we backtrack by removing the i -th item to restore the previous state to prepare for the next child node i+1.

This process follows the backtracking technique, which is characterized by:

• Brute-force: Evaluates all possible combinations that satisfy the constraints
• Incremental: Generates new combinations by adding one item at a time
• Pruning: If a combination fails to meet the constraints, all combinations derived from it can be discarded
• Backtracking: When a combination is invalid or fully explored, we revert to the previous state and explore other possibilities

What is dynamic programming?

The 0/1 knapsack problem can be solved using backtracking, but why do we need dynamic programming? What exactly is dynamic programming?

Let’s analyze the time complexity of the backtracking solution for Q2. Each node can call the recursive function up to N times, where N is the number of items in the candidate array. The maximal depth of the n-ary tree is W/S, where W is the weight limit and S is the smallest weight among the candidates. The total number of nodes in the tree determines the time complexity, as this is a tree traversal problem. Hence the time complexity is

The time complexity does not look good, as it results in an n-ary tree traversal problem. To optimize this, we should explore alternative approaches — perhaps using a binary tree traversal could be more efficient.

The reason we ended up with an n-ary tree is that child nodes are generated by iterating through the candidates. However, if we instead consider selecting or not selecting an item to generate child nodes, the structure transforms into a binary tree.

Now, let’s visualize the binary tree representation of this approach.

It is a binary tree, where each node stores information:

• Comb: The items included in this node’s combination
• Index: The position in the candidate list where an item can be either selected or excluded to generate two child nodes. The constraint that each item can be chosen only once, is the key to forming a binary tree
• W: The remaining weight limit, is updated as new items are added
• Profit: The total profit of the current combination

Below is the DFS recursive implementation for traversing the binary tree

class Solution {
  public:
    int solveKnapsack(vector<int> &profits, vector<int> &weights, int capacity) {
      if (profits.empty() || weights.empty() || capacity <= 0) return 0;

      vector<int> comb;
      return recurSearch(profits, weights, comb, 0, capacity, 0);
    }

    // Return the maximum profit of left tree and right tree of current node
    int recurSearch(const vector<int>& profits, const vector<int>& weights, 
                    vector<int>& comb, int index, int W, int profit) 
    {
      // Base cases
      if (W<0) return 0;  // Red nodes
      if (W==0) return profit;  // Green nodes
      if (index >= profits.size()) return profit;  // Blue nodes

      vector<int> left_comb = comb;
      left_comb.push_back(weights[index]);
      int left_max_profit = recurSearch(profits, weights, left_comb, index+1, 
                                        W-weights[index], profit+profits[index]);
      int right_max_profit = recurSearch(profits, weights, comb, index+1, W, profit);

      return std::max(left_max_profit, right_max_profit);
    }
  };

The comb argument is unnecessary, as a traversal path represents a combination, so we can remove it. Similarly, the profit argument can be eliminated since we only need to track the maximum profit, which is returned by the recursive function.

With these optimizations, the solution simplifies to the following.

class Solution {
  public:
    int solveKnapsack(vector<int> &profits, vector<int> &weights, int capacity) 
    {
      if (profits.empty() || weights.empty() || capacity <= 0) return 0;

      return recurSearch(profits, weights, 0, capacity);
    }

    // Return the maximum profit of left tree and right tree of current node
    int recurSearch(const vector<int>& profits, const vector<int>& weights, 
                    int index, int W) {
      // Base cases
      if (W<=0) return 0;
      if (index >= profits.size()) return 0;

      int left_max_profit=0;
      if (W >= weights[index])
        left_max_profit = profits[index] + recurSearch(profits, weights, index+1, W-weights[index]);
      int right_max_profit = recurSearch(profits, weights, index+1, W);

      return std::max(left_max_profit, right_max_profit);
    }
  };

The time complexity of this solution is

where n is the number of items. While this may be an improvement over traversing an n-ary tree, is there a way to optimize it further?

With the removal of the comb and profit arguments, let's also simplify the diagram.

As we can see, the two yellow nodes are identical, indicating an overlapping subproblem pattern. This is where dynamic programming becomes useful. A straightforward approach is to store the results of previously solved subproblems and reuse them whenever we encounter the same subproblems again.

class Solution {
  public:
    int solveKnapsack(vector<int> &profits, vector<int> &weights, int capacity) 
    {
      if (profits.empty() || weights.empty() || capacity <= 0) return 0;

      vector<vector<int>> memory(profits.size(), vector<int>(capacity+1, -1));
      return recurSearch(profits, weights, 0, capacity, memory);
    }

    // Return the maximum profit of left tree and right tree of current node
    int recurSearch(const vector<int>& profits, const vector<int>& weights, 
                    int index, int W, vector<vector<int>>& memory) {
      // Base cases
      if (W<=0) return 0;
      if (index >= profits.size()) return 0;

      if (memory[index][W] != -1) return memory[index][W];

      int left_max_profit=0;
      if (W >= weights[index])
        left_max_profit = profits[index] + recurSearch(profits, weights, index+1, W-weights[index], memory);
      int right_max_profit = recurSearch(profits, weights, index+1, W, memory);

      memory[index][W] = std::max(left_max_profit, right_max_profit);

      return memory[index][W];
    }
  };

The solution above follows a top-down dynamic programming approach with memoization. Alternatively, a bottom-up approach can also be used. However, we won’t get into that here, as the focus of this article is to compare backtracking vs dynamic programming.

In general, dynamic programming is used to solve problems that can be broken down into overlapping subproblems. Its key characteristics include:

• Brute-force: Evaluates all possible combinations that satisfy the constraints
• Overlapping subproblems: Identifies repeated computation, allowing DP to optimize the brute-force approach

Can we use dynamic programming to solve Q1?

Let’s summarize the key steps that led us to use dynamic programming for Q2,

• Replace the n-ary tree with a binary tree. This was crucial for Q2, but it is challenging for Q1 since each item can be selected multiple times.
• Optimize the recursive function to depend on only two dynamic arguments. This worked for Q2, but for Q1, we need to store all valid results, not just find the most optimized one, making it more complex.
• Identify overlapping subproblems. This step is difficult to achieve without the first two optimizations.

Given these challenges, applying dynamic programming to Q1 is not as straightforward.

4. Similarities and Differences

Similarities

• Brute-force. Both approaches evaluate all possible solutions
• Recursion. Both can be implemented recursively and represented using a tree structure

Differences

• Backtracking can solve some dynamic programming problems, but dynamic programming is not always applicable to backtracking problems
• Dynamic programming relies on overlapping subproblems, whereas backtracking does not
• Backtracking is commonly used when multiple valid solutions exist, while dynamic programming is primarily used for optimization problems that require finding the best possible solution