How to Think About Data Structure and Algorithm

Over the past few years, through continuous practice, reflection, and writing tutorials, my understanding of algorithms has gradually deepened. So today, I am writing another article, integrating multiple previous articles, and condensing my years of experience and thoughts into 7000 words to share with all of you.

This article mainly has two parts: one is my understanding of the essence of data structures and algorithms, and the other is a summary of various commonly used algorithms. The article doesn't contain much hardcore code; it's mostly my experience. It may not be very sophisticated, but it will surely help you avoid pitfalls and gain a more thorough understanding and mastery of algorithms.

Truly understanding the sentences above means you won't need to read this 7000-word article or even the dozens of algorithm tutorials and 500 exercises on this site.

If not understood, I will use the following several thousand words, along with dozens of upcoming articles and 500 exercises, to elaborate on the summary above. As you study, constantly reflecting on these sentences will greatly enhance your learning efficiency.

Storage Methods of Data Structures

There are only two storage methods for data structures: arrays (sequential storage) and linked lists (linked storage).

How should we understand this? Aren't there various data structures like hash tables, stacks, queues, heaps, trees, graphs, etc.?

When analyzing problems, one must think recursively, from top to bottom, from abstract to concrete. Listing so many structures at once refers to the higher-level constructs, while arrays and linked lists form the foundational structures. This is because those diverse data structures, at their core, are special operations on linked lists or arrays, differing only in their APIs.

For example, queues and stacks can be implemented using either linked lists or arrays. Using arrays requires handling resizing issues; using linked lists avoids this but requires more memory space to store node pointers.

The two storage methods for graph structures are adjacency lists and adjacency matrices. An adjacency list is essentially a linked list, and an adjacency matrix is a two-dimensional array. Adjacency matrices allow quick connectivity checks and can perform matrix operations to solve some problems. However, they consume a lot of space if the graph is sparse. Adjacency lists save space but are less efficient for many operations compared to adjacency matrices.

A hash table maps keys into a large array using a hash function. To resolve hash collisions, the chaining method employs linked list characteristics, making operations simple but requiring additional space for pointers. The linear probing method utilizes array characteristics for continuous addressing, eliminating the need for pointer storage but making operations slightly more complex.

In tree structures, an array-based implementation is a "heap," as a heap is a complete binary tree. Using arrays for storage eliminates the need for node pointers, and operations are relatively simple, as seen in applications like binary heaps. A linked list-based implementation is the common "tree" structure, which isn't necessarily a complete binary tree, making it unsuitable for array storage. This linked list "tree" structure has spawned various ingenious designs like binary search trees, AVL trees, red-black trees, interval trees, B-trees, and more to tackle different problems.

In summary, there are many types of data structures, and you can even invent your own. However, the underlying storage is either arrays or linked lists. Their advantages and disadvantages are as follows:

Arrays offer compact, continuous storage, allowing random access and quick element retrieval via indexing, and they save storage space. However, due to continuous storage, memory must be allocated in one go. Therefore, if an array needs to be resized, a larger memory block must be reallocated, and all data copied over, resulting in a time complexity of O(N). Additionally, inserting or deleting in the middle of an array requires shifting all subsequent data to maintain continuity, with a time complexity of O(N).

Linked Lists, with non-continuous elements connected via pointers to the next element's location, don't face the array's resizing issue. If the predecessor and successor of an element are known, pointers can be adjusted to delete or insert an element, with a time complexity of O(1). However, due to non-continuous storage, the address of an element can't be calculated from an index, thus preventing random access. Moreover, each element must store pointers to the locations of adjacent elements, consuming relatively more storage space.

Basic Operations of Data Structures

For any data structure, its basic operations are simply traversal + access, which can be further detailed as: add, delete, search, and update.

There are many types of data structures, but their purpose is the same: to efficiently add, delete, search, and update elements in different application scenarios. This is the mission of data structures.

How do we traverse + access? From a high-level perspective, there are only two forms of traversal + access for various data structures: linear and non-linear.

Linear traversal is typically represented by for/while iteration, while non-linear traversal is represented by recursion. More specifically, the following frameworks are used:

Array traversal framework, a typical linear iteration structure:

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // iterate through arr[i]
    }
}

void traverse(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        // iteratively access arr[i]
    }
}

def traverse(arr: List[int]):
    for i in range(len(arr)):
        # iterate over arr[i]

func traverse(arr []int) {
    for i := 0; i < len(arr); i++ {
        // iterate and access arr[i]
    }
}

var traverse = function(arr) {
  for (var i = 0; i < arr.length; i++) {
    // iterate and access arr[i]
  }
}

Linked list traversal framework, incorporating both iterative and recursive structures:

// basic singly linked list node
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // iteratively access p.val
    }
}

void traverse(ListNode head) {
    // recursively access head.val
    traverse(head.next);
}

// basic singly-linked list node
class ListNode {
    public:
        int val;
        ListNode* next;
};

void traverse(ListNode* head) {
    for (ListNode* p = head; p != nullptr; p = p->next) {
        // iteratively access p->val
    }
}

void traverse(ListNode* head) {
    // recursively access head->val
    traverse(head->next);
}

# basic single linked list node
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def traverse(head: ListNode) -> None:
    p = head
    while p is not None:
        # iteratively access p.val
        p = p.next

def traverse(head: ListNode) -> None:
    # recursively access head.val
    traverse(head.next)

// basic singly linked list node
type ListNode struct {
    val int
    next *ListNode
}

func traverse(head *ListNode) {
    for p := head; p != nil; p = p.next {
        // iteratively access p.val
    }
}

func traverse(head *ListNode) {
    // recursively access head.val
    traverse(head.next)
}

// basic single linked list node
class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function traverse(head) {
    for (var p = head; p != null; p = p.next) {
        // iteratively access p.val
    }
}

function traverse(head) {
    // recursively access head.val
    traverse(head.next);
}

Binary Tree Traversal Framework, a typical non-linear recursive traversal structure:

// basic binary tree node
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

// basic binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void traverse(TreeNode* root) {
    traverse(root->left);
    traverse(root->right);
}

# basic binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def traverse(root: TreeNode):
    traverse(root.left)
    traverse(root.right)

// basic binary tree node
type TreeNode struct {
    val int
    left *TreeNode
    right *TreeNode
}

// post-order traversal of binary tree
func traverse(root *TreeNode) {
    if root != nil {
        traverse(root.left)
        traverse(root.right)
    }
}

// basic binary tree node
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

var traverse = function(root) {
  if (root === null) return;
  traverse(root.left);
  traverse(root.right);
};

Do you see the similarity between the recursive traversal of a binary tree and the recursive traversal of a linked list? Also, notice the similarity between the structure of a binary tree and a singly linked list. If you add more branches, can you traverse an N-ary tree?

The binary tree framework can be extended to an N-ary tree traversal framework:

// basic N-ary tree node
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

// basic N-ary tree node
class TreeNode {
public:
    int val;
    vector<TreeNode*> children;
};

void traverse(TreeNode* root) {
    for (TreeNode* child : root->children)
        traverse(child);
}

# basic N-ary tree node
class TreeNode:
    val: int
    children: List[TreeNode]

def traverse(root: TreeNode) -> None:
    for child in root.children:
        traverse(child)

// basic N-ary tree node
type TreeNode struct {
    val int
    children []*TreeNode
}

func traverse(root *TreeNode) {
    for _, child := range root.children {
        traverse(child)
    }
}

// basic N-ary tree node
var TreeNode = function(val, children) {
  this.val = val;
  this.children = children;
};

// traverse N-ary tree
var traverse = function(root) {
  for (var i = 0; i < root.children.length; i++) {
    traverse(root.children[i]);
  }
};

Traversal of an N-ary tree can be extended to graph traversal since a graph is essentially a combination of several N-ary trees. Worried about cycles in the graph? It's simple, just use a boolean array visited to mark the nodes, as explained in detail in Graph Traversal.

The so-called framework is a routine. Whether it's adding, deleting, searching, or updating, these codes always follow the same structure. You can use this structure as an outline and add specific code to it based on the particular problem.

The Essence of Algorithms

If I had to summarize the essence of algorithms in one sentence, I would say it's "exhaustive search."

Some might argue, is the essence of all algorithm problems really exhaustive search? Are there no exceptions?

Of course, there are exceptions, such as problems that can be solved with one line of code. These problems are like brain teasers, where you solve them by observing patterns and finding the optimal solution. However, such algorithm problems are rare and not worth dwelling on. Another example is cryptography algorithms or machine learning algorithms. Their essence is not exhaustive search but the implementation of mathematical principles in programming. So, these kinds of algorithms are fundamentally mathematical and not within the scope of "data structures and algorithms" that we are discussing.

By the way, the "algorithms" that "algorithm engineers" work on and the "algorithms" in "data structures and algorithms" are entirely different concepts, to avoid misunderstanding among beginners.

For the former, the focus is on mathematical modeling and tuning parameters, where computers are merely tools for computation. For the latter, the focus is on computational thinking, requiring you to stand from a computer's perspective, abstract and simplify real-world problems, and then solve them using appropriate data structures.

So, don't think that mastering data structures and algorithms will make you an algorithm engineer, nor should you think that if you don't want to be an algorithm engineer, you don't need to learn data structures and algorithms.

Frankly, most development jobs involve working with existing development frameworks and rarely touch on underlying data structures and algorithm issues. But the fact remains that if you want a technical job, you can't avoid being tested on data structures and algorithms, as this knowledge is recognized as the fundamental skills of a programmer.

To distinguish, let's call the algorithms studied by algorithm engineers "mathematical algorithms," and the algorithms used in coding interviews "computer algorithms." My content mainly focuses on "computer algorithms."

This explanation should be quite clear. I guess most people's goal is to pass the algorithm test and get a job in development. Therefore, you really don't need much mathematical background; you just need to learn how to use computational thinking to solve problems.

Actually, computational thinking isn't that advanced. Think about the characteristics of a computer. What's the main feature? Speed. Your brain can process one thing per second, whereas a CPU can handle thousands of operations in the same time. So, the computer's way to solve problems is simple: exhaustive search.

When I first started learning, I also thought that computer algorithms were very sophisticated. Whenever I encountered a problem, I would wonder if I could derive a mathematical formula to get the answer instantly.

For example, if you tell someone who hasn't studied computer algorithms that you wrote an algorithm to calculate permutations and combinations, they might think you invented a formula to directly compute all possibilities. But in reality, there's nothing sophisticated about it. I will explain in Backtracking Algorithms for Permutations and Combinations that it essentially involves abstracting all possible permutations and combinations into a multi-branch tree structure, and then writing code to traverse this tree to collect all results. What's so magical about that?

The misunderstanding of computer algorithms might be a "side effect" from studying math. In math, you usually carefully observe, find geometric relationships, set up equations, and then calculate the answer. If you need to perform large-scale enumeration to find the answer, it likely means your problem-solving approach is flawed.

In contrast, the way computers solve problems is the opposite: leave the derivation of mathematical formulas to humans. If you can find some clever theorems, great. If not, just use exhaustive search, as long as the complexity is manageable. Theoretically, if you keep randomly shuffling an array, you'll eventually get a sorted result! Of course, this is not a good algorithm because who knows how long it will take to run.

In technical job tests and interviews, the algorithm questions often involve finding the maximum or minimum value. How do you find it? By enumerating all feasible solutions, you can find the optimal value. Essentially, that's all there is to it.

Challenges of Exhaustive Search

Different types of problems have different challenges. Some problems are hard because of "how to enumerate," while others are hard because of "how to cleverly enumerate."

Which algorithms are challenging because of "how to enumerate"? Generally, recursive problems, such as backtracking algorithms and dynamic programming algorithms.

Let's start with backtracking algorithms. Take the permutation and combination problems we learned in high school as an example. Back then, we could find patterns and deduce permutations and combinations on scratch paper: based on the possible choices for the first position, we fixed the first position and then looked at the possible choices for the second position, and so on. However, without training, it's difficult to use code to enumerate all permutations and combinations because it's hard to abstract this manual enumeration process into a programmable pattern.

First, you need to abstract the permutation and combination problem into a tree. Then, you need to precisely use code to traverse all nodes of this tree, ensuring no nodes are missed or repeated to write correct code. In the following chapters, I will first introduce The Core Framework of Backtracking Algorithms and then solve all subset and permutation combination problems at once in Solving Subset and Permutation Problems with Backtracking.

Dynamic programming is a bit harder than backtracking. Both are essentially enumeration, but their thinking patterns differ. Backtracking uses a "traversal" mindset, while dynamic programming uses a "problem decomposition" mindset.

So, do you understand why I said the difficulty of dynamic programming lies in "how to enumerate"? Normally, people don't think in such a peculiar way, but this method combined with computers is a game-changer. Therefore, you need to practice. Once you master it, you can write algorithms effortlessly, and they will always be correct.

In Core Framework of Dynamic Programming, I explained the process of solving dynamic programming problems. It essentially starts with writing a brute-force solution (state transition equation). Adding a memoization turns it into a top-down recursive solution. With some modifications, it becomes a bottom-up iterative solution. In Dimensionality Reduction in Dynamic Programming, I also discussed how to use space compression techniques to optimize the space complexity of dynamic programming algorithms.

Adding memoization and space compression techniques fall under "how to enumerate smartly". These are fixed patterns and not difficult. When you actually solve dynamic programming problems, you'll realize that you can't even come up with the state transition equation, meaning you can't write the brute-force solution in the first place. Hence, finding the state transition equation (how to enumerate) is the real challenge.

I specifically wrote Designing Dynamic Programming Algorithms: Mathematical Induction to tell you that the core of enumeration is mathematical induction. Clearly define the function, decompose the problem, and then use this definition to recursively solve sub-problems.

What is the challenge in algorithms regarding "how to enumerate smartly"? Many well-known non-recursive algorithm techniques fall into this category.

The simplest example is finding an element in a sorted array. Anyone can use a for loop to perform a brute-force search, but the binary search algorithm is a smarter way to enumerate, offering better time complexity.

Additionally, the previously mentioned Union Find algorithm provides an efficient technique for calculating connected components. Theoretically, you could determine if two nodes in a graph are connected using DFS/BFS brute-force search (enumeration), but the Union Find algorithm cleverly uses arrays to simulate tree structures, reducing the complexity of connectivity operations to $O(1)$.

This is an example of smart enumeration. Experts have invented these techniques, and once you've learned them, you can use them. Without learning, it might be challenging to come up with such approaches.

Another example is the greedy algorithm technique. The article When Experienced Developers Learn Greedy Algorithms explains that greedy algorithms involve identifying certain patterns (more formally known as the greedy choice property) in problems, allowing you to find solutions without exhaustively enumerating all possibilities.

Dynamic programming thoroughly enumerates all solutions without redundancy to find an optimal solution. In contrast, greedy algorithms can find answers without full enumeration, often making them more efficient, as seen in Using Greedy Algorithms to Solve the Jump Game. However, not all problems have the greedy choice property that allows for shortcuts, so while complete enumeration may be plain and tedious, it is universally applicable.

Below, I summarize some common algorithm techniques for your learning and reference.

Array/Singly Linked List Series Algorithms

A common technique for singly linked lists is the two-pointer method, which falls under the category of "smart enumeration." We've summarized all these techniques for you in Singly Linked List Two-Pointer Techniques. It's easy for those who know, and difficult for those who don't.

For example, to determine if a singly linked list has a cycle, the brute-force method might be to use a data structure like a HashSet to store visited nodes, and if you encounter a duplicate, there's a cycle, right? However, using fast and slow pointers can avoid the need for extra space, representing a smarter way to enumerate.

Common array techniques also involve the two-pointer method, which also falls under "smart enumeration." We've summarized all these techniques in Array Two-Pointer Techniques. It's easy for those who know, and difficult for those who don't.

Firstly, let's talk about binary search techniques, which can be considered as two pointers moving toward the center. If you're asked to find an element in an array, a for loop with $O(N)$ time complexity will definitely work, right? But binary search shows that if the array is sorted, it only requires a complexity of $O(logN)$. Isn't this a smarter search method?

The article Detailed Binary Search Framework provides a summary of binary search code templates, ensuring no boundary issues arise. Application of Binary Search summarizes the common traits of problems related to binary search and how to apply the idea of binary search to practical algorithms.

Next, let's discuss sliding window algorithm techniques, which are typical fast and slow two-pointer techniques. Using nested for loops with $O(N^2)$ time complexity will certainly enumerate all subarrays, and you will find the subarray that meets the requirements. However, in some scenarios, the sliding window algorithm can find the answer with a fast and slow pointer in just $O(N)$ time, representing a smarter way of enumeration.

The article Detailed Sliding Window Algorithm Framework introduces the applicable scenarios of the sliding window algorithm and a general code template, ensuring you write correct code. In Sliding Window Exercises, you'll be guided step-by-step on how to use the sliding window framework to solve various problems.

Finally, let's talk about prefix sum techniques and difference array techniques.

If you're frequently asked to calculate the sum of subarrays, using a for loop each time is definitely feasible, but the prefix sum technique precomputes a preSum array to avoid looping.

Similarly, if you're frequently asked to perform increment or decrement operations on subarrays, you can use a for loop each time, but the difference array technique maintains a diff array to avoid looping.

These are the main techniques for arrays and linked lists, and they're quite standard. Once you've seen them, applying them isn't too difficult. Now, let's move on to some slightly more challenging algorithms.

Binary Tree Algorithms Series

Regular readers know that I have repeatedly emphasized the importance of binary trees. The binary tree model is the foundation of almost all advanced algorithms. Many people struggle with understanding recursion, making it essential to practice binary tree-related problems.

As mentioned in the Binary Tree Essentials (Guiding Principles), the recursive solutions for binary tree problems can be categorized into two approaches. The first approach is to traverse the binary tree to find the answer, and the second approach is to compute the answer by decomposing the problem. These two approaches correspond to the Backtracking Algorithm Core Framework and the Dynamic Programming Core Framework respectively.

Traversal Thought Pattern

What does it mean to find the answer by traversing a binary tree?

For example, consider the problem of computing the maximum depth of a binary tree and implementing the maxDepth function. Writing your code like this is perfectly fine:

class Solution {

    // record the maximum depth
    int res = 0;
    // record the depth of the current node being traversed
    int depth = 0;

    // main function
    int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    // binary tree traversal framework
    void traverse(TreeNode root) {
        if (root == null) {
            // reach a leaf node
            res = Math.max(res, depth);
            return;
        }
        // pre-order traversal position
        depth++;
        traverse(root.left);
        traverse(root.right);
        // post-order traversal position
        depth--;
    }
}

class Solution {
public:

    // record the maximum depth
    int res = 0;
    // record the depth of the current node being traversed
    int depth = 0;

    // main function
    int maxDepth(TreeNode* root) {
        traverse(root);
        return res;
    }

    // binary tree traversal framework
    void traverse(TreeNode* root) {
        if (root == NULL) {
            // reached a leaf node
            res = max(res, depth);
            return;
        }
        // pre-order traversal position
        depth++;
        traverse(root->left);
        traverse(root->right);
        // post-order traversal position
        depth--;
    }
};

class Solution:
    def __init__(self):
        # record the maximum depth
        self.res = 0
        # record the depth of the current traversal node
        self.depth = 0
        
    def maxDepth(self, root: TreeNode) -> int:
        self.traverse(root)
        return self.res
        
    def traverse(self, root: TreeNode) -> None:
        if not root:
            # reached a leaf node
            self.res = max(self.res, self.depth)
            return
        # pre-order traversal position
        self.depth += 1
        self.traverse(root.left)
        self.traverse(root.right)
        # post-order traversal position
        self.depth -= 1

func maxDepth(root *TreeNode) int {
    // res records the maximum depth
    // depth records the depth of the current node being traversed
	res, depth := 0, 0
	traverse(root, &res, &depth)
	return res
}

func traverse(root *TreeNode, res *int, depth *int) {
	if root == nil {
		// reached a leaf node
		*res = max(*res, *depth)
		return
	}
	// pre-order traversal position
	*depth++
	traverse(root.left, res, depth)
	traverse(root.right, res, depth)
	// post-order traversal position
	*depth--
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var maxDepth = function(root) {
    // record the maximum depth
    let res = 0;
    // record the depth of the current node being traversed
    let depth = 0;

    // main function
    function traverse(root) {
        if (root === null) {
            // reached a leaf node
            res = Math.max(res, depth);
            return;
        }
        // pre-order traversal position
        depth++;
        traverse(root.left);
        traverse(root.right);
        // post-order traversal position
        depth--;
    }

    traverse(root);
    return res;
};

This logic uses the traverse function to go through all the nodes of the binary tree, maintaining a depth variable, and updates the maximum depth at the leaf nodes.

Does this code look familiar to you? Can you see the resemblance to the backtracking algorithm template?

If you're skeptical, compare it with the code for the permutation problem in the Core Framework of Backtracking Algorithms. The backtrack function is essentially the same as the traverse function, just with a different name. The overall logic is very similar:

class Solution {
    // record all permutations
    List<List<Integer>> res = new LinkedList<>();
    // record the current permutation being enumerated
    LinkedList<Integer> track = new LinkedList<>();

    // elements in track will be marked as true to avoid reuse
    boolean[] used;

    // main function, input a set of unique numbers, return all their permutations
    List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        
        backtrack(nums);
        return res;
    }

    // the core framework of the backtracking algorithm, traverse
    // the backtracking tree, collect all permutations at leaf
    void backtrack(int[] nums) {
        // reached a leaf node, elements in track form a permutation
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // exclude invalid choices
            if (used[i]) {

                // nums[i] is already in track, skip
                continue;
            }
            // make a choice
            track.add(nums[i]);
            used[i] = true;

            // enter the next level of the recursion tree
            backtrack(nums);
            
            // undo the choice
            track.removeLast();
            used[i] = false;
        }
    }
}

class Solution {
public:
    // record all permutations
    vector<vector<int>> res;
    // record the current permutation being enumerated
    vector<int> track;

    // elements in track will be marked as true to avoid reuse
    vector<bool> used;

    // main function, input a set of unique numbers, return their permutations
    vector<vector<int>> permute(vector<int>& nums) {
        used = vector<bool>(nums.size(), false);
        
        backtrack(nums);
        return res;
    }

    // core framework of the backtracking algorithm, traverse the
    // backtracking tree, collect all permutations on the leaf
    void backtrack(vector<int>& nums) {
        // reached a leaf node, elements in track form a permutation
        if (track.size() == nums.size()) {
            res.push_back(track);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            // exclude illegal choices
            if (used[i]) {
                // nums[i] is already in track, skip
                continue;
            }
            // make a choice
            track.push_back(nums[i]);
            used[i] = true;

            // enter the next level of the recursive tree
            backtrack(nums);
            
            // undo the choice
            track.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # record all permutations
        res = []
        # record the current permutation being enumerated
        track = []

        # elements in track will be marked as true to avoid reuse
        used = [False] * len(nums)

        # main function, input a set of unique numbers, return all their permutations
        def backtrack(nums):
            # reach a leaf node, elements in track form a permutation
            if len(track) == len(nums):
                res.append(track[:])
                return

            for i in range(len(nums)):
                # exclude invalid choices
                if used[i]:
                    # nums[i] is already in track, skip
                    continue
                # make a choice
                track.append(nums[i])
                used[i] = True

                # enter the next level of the recursion tree
                backtrack(nums)

                # undo the choice
                track.pop()
                used[i] = False

        backtrack(nums)
        return res

func permute(nums []int) [][]int {
    // record all permutations
    var res [][]int
    // record the current permutation being enumerated
    var track []int

    // elements in track are marked as true to avoid reuse
    used := make([]bool, len(nums))

    // main function; input a set of distinct numbers and return their permutations
    backtrack(nums, &res, &track, used)
    return res
}

// core framework of backtracking algorithm, traverse the
// backtracking tree to collect all permutations at leaf nodes
func backtrack(nums []int, res *[][]int, track *[]int, used []bool) {
    // reach a leaf node, elements in track form a permutation
    if len(*track) == len(nums) {
        tmp := make([]int, len(*track))
        copy(tmp, *track)
        *res = append(*res, tmp)
        return
    }

    for i := 0; i < len(nums); i++ {
        // exclude invalid choices
        if used[i] {
            // nums[i] is already in track, skip it
            continue
        }
        // make a choice
        *track = append(*track, nums[i])
        used[i] = true

        // enter the next level of the recursion tree
        backtrack(nums, res, track, used)

        // undo the choice
        *track = (*track)[:len(*track)-1]
        used[i] = false
    }
}

var permute = function(nums) {
    // record all permutations
    let res = [];
    // record the current permutation being explored
    let track = [];

    // elements in track will be marked as true to avoid reuse
    let used = new Array(nums.length).fill(false);

    // main function, input a set of unique numbers, return their permutations
    function backtrack(nums) {
        // reached a leaf node, elements in track form a permutation
        if (track.length === nums.length) {
            res.push(track.slice());
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            // exclude invalid choices
            if (used[i]) {
                // nums[i] is already in track, skip it
                continue;
            }
            // make a choice
            track.push(nums[i]);
            used[i] = true;

            // enter the next level of the recursive tree
            backtrack(nums);

            // undo the choice
            track.pop();
            used[i] = false;
        }
    }

    backtrack(nums);
    return res;
};

Although the code looks lengthy, isn't it essentially a traversal of a multi-branch tree? Therefore, the core of the backtracking algorithm is traversing a multi-branch tree. As long as you can abstract the problem into a tree structure, you can solve it using the backtracking algorithm.

Problem Decomposition Approach

What does it mean to compute the answer by decomposing the problem?

For example, when calculating the maximum depth of a binary tree, you can also write the following solution:

// definition: input the root node, return the maximum depth of this binary tree
int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}
	// recursively calculate the maximum depth of left and right subtrees
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);
	// the maximum depth of the whole tree is the
// maximum depth of the left and right subtrees plus
	int res = Math.max(leftMax, rightMax) + 1;

	return res;
}

// Definition: input the root node, return the maximum depth of the binary tree
int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    // Recursively calculate the maximum depth of the left and right subtrees
    int leftMax = maxDepth(root->left);
    int rightMax = maxDepth(root->right);
    // The maximum depth of the whole tree is the
    // maximum depth of the left and right subtrees
    int res = max(leftMax, rightMax) + 1;

    return res;
}

# Definition: input the root node, return the maximum depth of this binary tree
def maxDepth(root: TreeNode) -> int:
    if root is None:
        return 0
    # Recursively calculate the maximum depth of the left and right subtrees
    leftMax = maxDepth(root.left)
    rightMax = maxDepth(root.right)
    # The maximum depth of the entire tree is the
    # maximum depth of the left and right subtrees
    res = max(leftMax, rightMax) + 1

    return res

// Definition: input the root node, return the maximum depth of this binary tree
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // recursively calculate the maximum depth of the left and right subtrees
    leftMax := maxDepth(root.left)
    rightMax := maxDepth(root.right)
    // the maximum depth of the entire tree is the
    // maximum depth of the left and right subtrees
    res := max(leftMax, rightMax) + 1

    return res
}

// helper function
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// Definition: input the root node, return the maximum depth of this binary tree
var maxDepth = function(root) {
    if (root == null) {
        return 0;
    }
    // recursively calculate the maximum depth of the left and right subtrees
    let leftMax = maxDepth(root.left);
    let rightMax = maxDepth(root.right);
    // the maximum depth of the entire tree is the
    // maximum depth of the left and right subtrees
    let res = Math.max(leftMax, rightMax) + 1;

    return res;
};

Do you find this code familiar? Does it remind you of the dynamic programming approach?

Take a look at the brute-force solution for the coin change problem in the Core Framework of Dynamic Programming:

// Definition: input the amount, return the minimum number of coins to make up the amount
int coinChange(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // Recursively calculate the minimum number of coins to make up amount - coin
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) continue;
        // Minimum number of coins to make up the amount
        res = Math.min(res, subProblem + 1);
    }

    return res == Integer.MAX_VALUE ? -1 : res;
}

// Definition: input the amount, return the minimum number of coins needed to make up the amount
int coinChange(vector<int>& coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = INT_MAX;
    for (int coin : coins) {
        // recursively calculate the minimum number of coins needed to make up amount - coin
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) continue;
        // the minimum number of coins needed to make up the amount
        res = min(res, subProblem + 1);
    }

    return res == INT_MAX ? -1 : res;
}

def coinChange(coins: List[int], amount: int) -> int:
    # base case
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    # res is the minimum number of coins to make up the amount
    res = float('inf')
    for coin in coins:
        # recursively calculate the minimum number of coins to make up amount - coin
        sub_problem = coinChange(coins, amount - coin)
        if sub_problem == -1:
            continue
        # take the minimum value
        res = min(res, sub_problem + 1)

    return -1 if res == float('inf') else res

func coinChange(coins []int, amount int) int {
    // base case
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }

    res := math.MaxInt32
    for _, coin := range coins {
        // recursively calculate the minimum number of coins to make up amount - coin
        subProblem := coinChange(coins, amount-coin)
        if subProblem == -1 {
            continue
        }
        // minimum number of coins to make up amount
        res = min(res, subProblem+1)
    }

    if res == math.MaxInt32 {
        return -1
    }
    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

var coinChange = function(coins, amount) {
    // base case
    if (amount === 0) return 0;
    if (amount < 0) return -1;

    let res = Number.MAX_VALUE;
    for (let coin of coins) {
        // recursively calculate the minimum number of coins to make up amount - coin
        let subProblem = coinChange(coins, amount - coin);
        if (subProblem === -1) continue;
        // the minimum number of coins to make up amount
        res = Math.min(res, subProblem + 1);
    }

    return res === Number.MAX_VALUE ? -1 : res;
};

Adding a memo (memoization) to this brute-force solution turns it into a top-down dynamic programming solution. If you compare it with the solution for finding the maximum depth of a binary tree, don't you find them very similar?

Expanding Ideas

If you understand the difference between the two solutions for the maximum depth problem, let's build on that. Let me ask you, how do you write the pre-order traversal for a binary tree?

I believe everyone will scoff at this question and can write the following code without hesitation:

List<Integer> res = new LinkedList<>();

// return the preorder traversal result
List<Integer> preorder(TreeNode root) {
    traverse(root);
    return res;
}

// binary tree traversal function
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // preorder traversal position
    res.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

vector<int> res;

// return the preorder traversal results
vector<int> preorder(TreeNode* root) {
    traverse(root);
    return res;
}

// binary tree traversal function
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // preorder traversal position
    res.push_back(root->val);
    traverse(root->left);
    traverse(root->right);
}

class Solution:
    def __init__(self):
        # create a list as the result container
        self.res = []

    # return the preorder traversal result
    def preorder(self, root: TreeNode) -> List[int]:
        self.traverse(root)
        return self.res

    # binary tree traversal function
    def traverse(self, root: TreeNode) -> None:
        if not root:
            return
        # position for preorder traversal
        self.res.append(root.val)
        self.traverse(root.left)
        self.traverse(root.right)

// return the preorder traversal result
func preorder(root *TreeNode) []int {
    var res []int
    traverse(root, &res)
    return res
}

// binary tree traversal function
func traverse(root *TreeNode, res *[]int) {
    if root == nil {
        return
    }
    // preorder traversal position
    *res = append(*res, root.Val)
    traverse(root.Left, res)
    traverse(root.Right, res)
}

// return the preorder traversal result
function preorder(root) {
    let res = [];

    // binary tree traversal function
    function traverse(root) {
        if (root === null) {
            return;
        }
        // preorder traversal position
        res.push(root.val);
        traverse(root.left);
        traverse(root.right);
    }

    traverse(root);
    return res;
}

However, considering the two different thought processes mentioned above, can the traversal of a binary tree also be solved by breaking down the problem?

Let's observe the characteristics of the preorder traversal result of a binary tree:

Notice the result of the preorder traversal: the root node's value is first, followed by the preorder traversal result of the left subtree, and finally the preorder traversal result of the right subtree.

Do you sense anything from this? In fact, you can completely rewrite the preorder traversal code by using a problem decomposition approach:

// Definition: input the root node of a binary tree,
// return the preorder traversal result of this tree
List<Integer> preorder(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    // The result of preorder traversal, root.val is first
    res.add(root.val);
    // Followed by the preorder traversal result of the left subtree
    res.addAll(preorder(root.left));
    // Finally followed by the preorder traversal result of the right subtree
    res.addAll(preorder(root.right));
    return res;
}

// Definition: input the root of a binary tree,
// return the preorder traversal result of this tree
vector<int> preorder(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) {
        return res;
    }
    // The preorder traversal result, root->val is first
    res.push_back(root->val);
    // Followed by the preorder traversal result of the left subtree
    vector<int> left = preorder(root->left);
    res.insert(res.end(), left.begin(), left.end());
    // Finally, followed by the preorder traversal result of the right subtree
    vector<int> right = preorder(root->right);
    res.insert(res.end(), right.begin(), right.end());
    return res;
}

from typing import List

# Definition: Given the root node of a binary tree,
# return the preorder traversal result of this tree
def preorder(root: TreeNode) -> List[int]:
    res = []
    if not root:
        return res
    # In the result of preorder traversal, root.val is the first
    res.append(root.val)
    # Then append the preorder traversal result of the left subtree
    res.extend(preorder(root.left))
    # Finally, append the preorder traversal result of the right subtree
    res.extend(preorder(root.right))
    return res

// Definition: Input the root node of a binary tree,
// return the preorder traversal result of this tree
func preorder(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    // The result of preorder traversal, root.val is the first
    res = append(res, root.val)
    // Followed by the preorder traversal result of the left subtree
    res = append(res, preorder(root.left)...)
    // Finally followed by the preorder traversal result of the right subtree
    res = append(res, preorder(root.right)...)
    return res
}

// Definition: given the root of a binary tree,
// return the preorder traversal result of this tree
var preorder = function(root) {
    var res = [];
    if (root === null) {
        return res;
    }
    // In the preorder traversal result, root.val is the first
    res.push(root.val);
    // Followed by the preorder traversal result of the left subtree
    res = res.concat(preorder(root.left));
    // Finally followed by the preorder traversal result of the right subtree
    res = res.concat(preorder(root.right));
    return res;
};

See, this is how to write a pre-order traversal of a binary tree using the problem decomposition thinking mode. Writing in-order and post-order traversals is similar.

Level Order Traversal

Besides dynamic programming, backtracking (DFS), and divide and conquer, another commonly used algorithm is BFS. The core framework of the BFS algorithm is adapted from the following level order traversal code of a binary tree:

// Input the root node of a binary tree, perform level-order traversal on the binary tree
void levelTraverse(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    int depth = 1;
    // Traverse each level of the binary tree from top to bottom
    while (!q.isEmpty()) {
        int sz = q.size();
        // Traverse each node of the level from left to right
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();

            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

// input the root node of a binary tree, perform a level order traversal of the tree
int levelTraverse(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);

    int depth = 0;
    // traverse each level of the binary tree from top to bottom
    while (!q.empty()) {
        int sz = q.size();
        // traverse each node of the level from left to right
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
    return depth;
}

# input the root of a binary tree, perform level order traversal of this binary tree
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = collections.deque()
        q.append(root)
        res = []
        while q:
            sz = len(q)
            tmp = []
            for i in range(sz):
                cur = q.popleft()
                tmp.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(tmp)
        return res

// Input the root node of a binary tree and perform level order traversal of this binary tree
func levelTraverse(root *TreeNode) {
    if root == nil {
        return
    }

    q := make([]*TreeNode, 0)
    q = append(q, root)
    depth := 1

    // Traverse each level of the binary tree from top to bottom
    for len(q) > 0 {
        sz := len(q)

        // Traverse each node of each level from left to right
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]

            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right) 
            }
        }
        depth++
    }
}

// input the root node of a binary tree, perform level-order traversal of this binary tree
var levelTraverse = function(root) {
    if (root == null) return 0;
    var q = [];
    q.push(root);

    var depth = 1;
    // traverse each level of the binary tree from top to bottom
    while (q.length > 0) {
        var sz = q.length;
        // traverse each node of each level from left to right
        for (var i = 0; i < sz; i++) {
            var cur = q.shift();

            if (cur.left != null) {
                q.push(cur.left);
            }
            if (cur.right != null) {
                q.push(cur.right);
            }
        }
        depth++;
    }
}

Moreover, graph-related algorithms are an extension of binary tree algorithms.

For example, the articles Graph Basics, Cycle Detection and Topological Sorting, and Bipartite Graph Detection Algorithm utilize DFS algorithms. Additionally, the Dijkstra Algorithm Template is a modified BFS algorithm combined with an array similar to a dynamic programming table.

Alright, that’s pretty much it. The essence of these algorithms is exhaustive search on binary (or multi-way) trees. Whenever possible, you can reduce redundant calculations and improve efficiency through techniques like pruning or memoization. That's all there is to it.

Final Summary

Many readers ask me what the correct approach to solving algorithm problems is. I believe the right approach should be such that solving one problem gives you the experience of solving ten. Otherwise, with over 2000 problems on LeetCode, do you plan to solve them all?

So how can you achieve this? You need a framework mindset, learn to extract the key points, and look for the unchanging elements. An algorithmic technique can be wrapped into thousands of problems. If you can see through their essence at a glance, then a thousand problems are equivalent to one, so why waste time doing them all?

This is the power of having a framework, ensuring that even when you're about to fall asleep, you can still write correct programs; even if you haven't learned much, this way of thinking can put you a level above others.

Teaching someone to fish is better than giving them a fish. Algorithms are not difficult; anyone can learn them well with the right mindset. I hope you can develop a systematic way of thinking with me and enjoy mastering algorithms, rather than being controlled by them.