Improve Brute Force

6 min readJan 4, 2020

Introduction

Brute force is the basis of the algorithms. You should be comfortable implementing a brute force solution for any problems. I believe algorithms can be divided into 2 groups; brute-force based and the other (I will call these smart algorithms). Brute force is a very generic algorithm that has wide applicability. Therefore, it’s essential to know the basis of that. In this article, I explain naive brute-force algorithms and their improvements.

What will be covered

Search Tree, DFS(Depth-First Search), BFS(Breath-First Search), Prunning, Dynamic Programming.

Search Tree

Before implementing a brute force algorithm, we need to build a search tree containing all the states you need to visit. Let’s think about a search tree for the problem below.

Can you make a given target number combining (adding) some numbers from a given number list?

This is called the Subset Sum Problem. For each number, you can choose to add or not to add. Therefore, the search tree of this problem looks like the figure below.

The most naive brute-force algorithms visit all the nodes in the search tree. When we don’t have smart algorithms, which solves a problem much faster than brute-force based algorithms, we have to implement a brute-force based algorithm. Let me introduce a term here; evaluation-ready node, a node that is ready to be evaluated. All the nodes in the search tree are either evaluation ready or not. In the search tree above, only leaf nodes are evaluation-ready since there are the states after deciding all the nodes either to be used or not to be used. Some search trees only contain evaluation-ready nodes including their root node. An example of this is the Equal Cost Shortest Path Problem, which will be explained in the BFS section later.

DFS (Depth-First Search)

This is the most basic way to explore a search tree. We start from the root node. Next, we dive as deep as possible. When we get stuck, we come back until we have a different route to go. We repeat this process until we visit all the nodes in the search tree.

How do we implement this? On a non-evaluation-ready node, we first evaluate all of its child nodes, one by one. Using these evaluation values, we decide the evaluation of the node. In the Subset Sum Problem, if any of the child nodes’ evaluation is true, the evaluation of the node becomes true. Note that the evaluation of children happens cascadingly until it reaches an evaluation-ready node. This corresponds with the explanation “we dive as deep as possible”. On an evaluation-ready node, we can evaluate it. In the Subset Sum Problem, the evaluation is sum == target. After evaluating a node, we go back to its parent node. The parent node is in charge of finding a different route. If the parent node does not have another route to go, it again goes back to its parent. DFS is typically implemented with recursion. Look at the example below.

This is implicitly using a stack by recursion. Of course, you can write DFS without a recursion. In this way, you can finish the loop with ease. See the example below.

As you can see, DFS with recursion has shorter code since it does not need to use a stack explicitly and can store states with ease as method arguments.

BFS (Breadth-First Search)

This is another way to implement a brute force. Unlike DFS, it visits nodes from the shallowest to the deepest. To do this, BFS utilizes a queue.

This implementation is really similar to the one of DFS with an explicit stack. Again, DFS with recursion has a shorter code than this for the same reason that I explained above in the DFS section. Also, BFS consumes more memory space than DFS does. In BFS, the space complexity is the size of the queue, which is O(n) where n is the size of the states. In DFS, the space complexity is the size of the stack, which is O(d) where d is the max depth of the search tree. Because of this, DFS is often preferred for most of the brute force approaches.

One important exception, however, is the Equal Cost Shortest Path Problem.

You are in a maze, points of which are represented by (x, y). You start from a starting point(sx, sy) and you need to go to an end point(ex, ey). You can go to one of the vertically or horizontally adjacent points within a move unless there is a building on the point. What is the minimum number of moves you need to make to reach the end point (ex, ey)?

This is an equal cost shortest path problem where its cost is 1. The state of this problem is represented by (x, y, distance(# of moves made so far)). Whenever you visit a point (x, y), you check the distance and update the minimum distance of (x, y) if the distance is smaller than the current minimum distance value. Obviously, the answer is the minimum distance of (ex, ey) after running a brute force algorithm, DFS or BFS, whichever you prefer. If you observe this carefully, however, as long as you visit each point from the closest to the farthest, you don’t need to re-visit the same points later since the distance in the state of revisit is never smaller than the distance in the state of the first visit. This is easily implemented by BFS by keeping track of visited points. If the point is visited previously, you can just skip the process for the point.

Pruning

Pruning is a way to improve your brute force. What we do is that we skip computations wherever we can. For the examples above, assuming all the numbers are non-negative, we can just put the below at the beginning of the loop because adding numbers to sum is not gonna help here.

if (sum > target) continue;

Pruning surely makes the code faster, but it is hard to estimate how much it improves the code since it depends on the input data. Note that the theoretical computation time remains the same.

DP (Dynamic Programming)

Dynamic Programming is often the most effective way to improve brute-force algorithms. When we see a lot of duplicated states in the search tree, it is a good sign. We can treat them as the same states, which leads to a reduction of time complexity. There are mainly two ways to implement DP: memorization (top-down) and tabulation (bottom-up). Since memorization is easy to implement for those who are familiar with DFS, I will show the example of memorization for the Subset Sum Problem here.

Here, we are evaluating nodes with the same (index, sum) state at most once by putting the results to the memo table before returning from the function. How much did this make the code faster? The naive dfs takes O(2 ** n) where n = nums.length since we have 2 ** n nodes to evaluate. With memorization, the time complexity becomes O(n * target) by avoiding evaluations for duplicated nodes. When target is a small number, this is a huge improvement. For instance, for n = 100 and target = 10000, the naive dfs has 2 ** 100 = 1,267,650,600,228,229,401,496,703,205,376 nodes to evaluate whereas the memorization has 100 * 10000 = 1,000,000 nodes.

Applying dynamic programming, however, is not easy. It is all about reducing the nodes to evaluate, but this requires a lot of practice since how to efficiently reduce nodes depends on the problem. The most efficient way to learn DP is I believe to solve many dynamic programming questions at competitive programming sites like TopCoder, Codeforces, and AtCoder. DP is as important as major algorithms like Dijkstra and KMP because it is a generic idea with a wide range of applicabilities. I will explain typical problems solved by dynamic programming in another article.

Summary

The most naive ways to implement brute force are DFS and BFS.
DFS uses less memory than BFS does.
DFS with recursion results in shorter code than BFS.
Pruning skips computations wherever possible.
Effectiveness of pruning is hard to estimate since it depends on the input data
DP is a generic way to drastically improve a brute force.
Applying DP requires a lot of experience.
Practice DP at competitive programming sites.

Thank you!

Shoya