How to Think About Data Structure and Algorithm

This article provides an overview of all the content on this site in two main parts: first, my understanding of the essence of data structures and algorithms; second, a summary of commonly used algorithms.

There is no complex code in this article. It is based on my experience and will help you avoid detours and deeply understand and master algorithms.

Summary of All Data Structures and Algorithms

All data structures are essentially transformations of arrays (sequential storage) and linked lists (linked storage).

The key point of data structures is in traversal and access, including basic operations such as adding, deleting, searching, and updating.

All algorithms are essentially brute-force.

The key to brute-force is no omission and no redundancy. Mastering algorithm frameworks allows for no omission; making full use of information ensures no redundancy.

If you truly understand the sentences above, you would not need to read the 7,000 words in this article, nor the dozens of algorithm tutorials and exercises on this site.

If you do not understand, then I will use the following thousands of words, as well as the upcoming articles and exercises, to explain these two sentences. While learning, always keep these two sentences in mind—they will greatly improve your learning efficiency.

Storage Methods of Data Structures

There are only two storage methods for data structures: Array (Sequential Storage) and Linked List (Linked Storage).

How should we understand this statement? Aren't there other data structures such as hash tables, stacks, queues, heaps, trees, graphs, etc.?

When analyzing issues, it's essential to have a recursive mindset, moving from the top down, from abstraction to concreteness. Listing many structures at the start overlooks that these belong to higher-level constructs, whereas arrays and linked lists form the foundational structure. All those diverse data structures ultimately originate from 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. When using arrays, one must handle the issues of resizing; linked lists do not have this problem but require more memory space to store node pointers.

The two storage methods for graph structures are adjacency lists and adjacency matrices. An adjacency list is a linked list, while an adjacency matrix is a two-dimensional array. Adjacency matrices quickly determine connectivity and allow matrix operations to solve certain problems, but are space-consuming for sparse graphs. Adjacency lists save space, though many operations are less efficient than with adjacency matrices.

A hash table maps keys to a large array using a hash function. To resolve hash collisions, the chaining method uses linked list characteristics, which simplifies operations but requires extra space for pointers; the linear probing method utilizes array characteristics for continuous addressing, eliminating the need for pointer storage, but the operations are slightly more complex.

In tree structures, using an array results in a "heap" since a heap is a complete binary tree, and storing it in an array requires no node pointers, simplifying operations. A classic example is binary heap. Using linked lists results in the common "tree," which is unsuitable for array storage as it may not be a complete binary tree. Therefore, various ingenious designs are derived from this linked list "tree" structure to tackle different problems, such as binary search trees, AVL trees, red-black trees, interval trees, B-trees, and more.

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:

Array is compactly and continuously stored, allowing random access and quick retrieval of elements via indexing while relatively conserving storage space. However, due to continuous storage, memory space must be allocated in one go, so resizing an array requires reallocating a larger space and copying all data, leading to a time complexity of O(N). Moreover, to insert or delete elements in the middle of an array, all subsequent data must be shifted to maintain continuity, resulting in a time complexity of $O(N)$.

Linked List elements are not continuous but are connected via pointers to the next element's location, avoiding the resizing issues of arrays. If the predecessor and successor of an element are known, the element can be deleted or a new one inserted by manipulating pointers, with a time complexity of $O(1)$. However, due to non-continuous storage space, the corresponding element's address cannot be calculated from an index, prohibiting random access. Each element must store pointers to 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 were to summarize in one sentence, I would say the essence of algorithms is "brute-force search".

Some may disagree, questioning if all algorithm problems fundamentally rely on brute-force. Are there no exceptions?

Certainly, there are exceptions. For instance, in problems solvable with a single line of code, these resemble brain teasers where solutions are found through observation and pattern recognition to arrive at the optimal solution. However, these types of algorithm problems are rare and shouldn't be overly concerning. Additionally, cryptographic algorithms and machine learning algorithms do not rely on brute-force but on mathematical principles implemented through programming, thus their essence is mathematical and outside the scope of "data structures and algorithms".

It's worth emphasizing that the "algorithms" worked on by "algorithm engineers" are entirely different from the "algorithms" in "data structures and algorithms". This is to prevent any misunderstanding among beginner readers.

For algorithm engineers, the focus is on mathematical modeling and tuning parameters, where computers are merely tools for computation. In contrast, the focus in data structures and algorithms is on computational thinking, requiring one to simplify real-world problems from a computer's perspective and solve them using appropriate data structures.

Therefore, do not assume that mastering data structures and algorithms will qualify you to be an algorithm engineer, nor think that you don't need to learn them if you don't plan to become one.

Frankly, most development jobs involve working with existing frameworks, rarely dealing with low-level data structures and algorithms. However, another truth is that if you seek a technical position, knowledge of data structures and algorithms is unavoidable, as these are recognized as fundamental skills for programmers.

To differentiate, we might refer to the algorithms studied by algorithm engineers as "mathematical algorithms" and those relevant to coding interviews as "computer algorithms". My content primarily 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 makes an algorithm challenging is "how to smartly perform an exhaustive search." Some 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 perform the search, with better time complexity.

In addition, the previous article on the Union Find algorithm introduces an efficient technique for calculating connected components. Theoretically, to determine if two nodes in a graph are connected, a brute-force search using DFS/BFS would work. However, the Union Find algorithm cleverly uses arrays to simulate tree structures, reducing the complexity of connectivity-related operations to $O(1)$.

These are examples of smart exhaustive search techniques. Experts have invented these methods; once you've learned them, you can use them. Without learning, it's challenging to devise such approaches on your own.

Another example is the greedy algorithm technique. The previous article When Experienced Drivers Learn Greedy Algorithms shows that the greedy algorithm involves identifying certain patterns (formally known as the greedy choice property) in a problem, allowing you to find the answer without exhaustively searching all solutions.

Dynamic programming at least performs a non-redundant exhaustive search for all solutions to find an optimal value. In contrast, a greedy algorithm can find the answer without searching all solutions, which is why, as shown in the article Using Greedy Algorithms to Solve Jump Game, the efficiency of greedy algorithms can surpass dynamic programming. Of course, not all problems have a greedy choice property that allows shortcuts. Therefore, while a complete exhaustive search may be plain and tedious, it is always applicable.

Below, I provide a summary of 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 brute-force". Summary of Two-Pointer Techniques for Singly Linked Lists provides a complete overview. For those who understand, it's easy; for those who don't, it's challenging.

For example, to determine if a singly linked list has a cycle, the brute-force method would involve using a data structure like a HashSet to store visited nodes, identifying a cycle when a duplicate is found. However, using fast and slow pointers can avoid additional space usage, which is a smarter brute-force approach.

Common techniques for arrays also involve the two-pointer method, which is part of "smart brute-force". Summary of Two-Pointer Techniques for Arrays covers everything. For those who understand, it's easy; for those who don't, it's challenging.

Firstly, the binary search technique can be categorized as two pointers moving from both ends to the center. If tasked with searching for an element in an array, a for loop with $O(N)$ time complexity can certainly accomplish the task. However, binary search shows that if the array is sorted, it only requires $O(logN)$ complexity, which is a smarter search method.

Detailed Framework of Binary Search provides a code template to ensure no boundary issues arise. Application of Binary Search Algorithms summarizes commonalities in binary search-related problems and how to apply the binary search concept to real-world algorithms.

Next, the Sliding Window Algorithm Technique is a typical fast and slow pointer method. Using nested for loops with $O(N^2)$ time complexity will certainly enumerate all subarrays and find those that meet the requirements. However, the sliding window algorithm demonstrates that in certain scenarios, using two pointers, one fast and one slow, only $O(N)$ time is needed to find the answer, which is a smarter brute-force approach.

Detailed Framework of Sliding Window Algorithm introduces applicable scenarios and a general code template for sliding window algorithms, ensuring you write correct code. Sliding Window Exercises guides you step by step to solve various problems using the sliding window framework.

Finally, the Prefix Sum Technique and Difference Array Technique.

If frequently required to calculate the sum of subarrays, using a for loop each time is feasible, but the prefix sum technique precomputes a preSum array to avoid loops.

Similarly, if frequently required to perform increment and decrement operations on subarrays, using a for loop each time is feasible, but the difference array technique maintains a diff array to avoid loops.

These are the main techniques for arrays and linked lists, which are relatively fixed. Once you've encountered them, applying them isn't too difficult. Let's move on to some slightly more challenging algorithms.

Binary Tree Algorithms

If you have read my articles before, you know how important binary trees are. I have mentioned this many times. The binary tree model is the base of almost all advanced algorithms. If you don't really understand recursion, you should practice more binary tree problems.

As mentioned in Binary Tree Mindset (Summary), there are two main ways to solve binary tree problems with recursion. The first way is to traverse the whole tree to get the answer. The second way is to split the problem into subproblems and combine the answers. These two methods match the Backtracking Core Framework and the Dynamic Programming Core Framework respectively.

Traversal Thinking

What does it mean to get the answer by traversing the whole binary tree?

For example, if you are asked to implement a maxDepth function to calculate the maximum depth of a binary tree, you can write the code like this:

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 nodes
    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 nodes
    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 one
	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 plus one
    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 plus one
    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 plus one
    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 plus one
    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;
};

You see, this is how you use the problem decomposition method to write preorder traversal for a binary tree. If you want to write inorder or postorder traversal, the idea is similar.

Level Order Traversal

Besides dynamic programming, backtracking (DFS), and divide and conquer, another common algorithm is BFS. The core BFS framework is built from the following level order traversal code for binary trees:

// Input the root node of a binary tree, perform level-order traversal on the binary tree
void levelTraverse(TreeNode root) {
    if (root == null) return;
    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;
    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)
        depth = 0
        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)
            depth += 1

// 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;
    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++;
    }
}

Going further, many graph algorithms are extensions of binary tree algorithms.

For example, Graph Basics, Cycle Detection and Topological Sort, and Bipartite Graph Check all use the DFS algorithm. The Dijkstra Algorithm Template is a modified BFS with an array similar to a dp table.

That's about it. At their core, these algorithms are all about brute-forcing through binary (or multi-way) trees. If possible, you can prune branches or use memoization to reduce repeated work and improve efficiency. That's the main idea.

Final Summary

Many readers ask me what is the right way to practice coding problems. I think the right way is to get the result of solving ten problems by doing one, otherwise, with 2000 problems on LeetCode, do you really want to solve them all one by one?

So how do you do that? You need to have a framework mindset. Learn to focus on the key points and find what stays the same among problems. One algorithm technique can be wrapped into thousands of problems. If you can see through their essence at a glance, then a thousand problems become one, so why waste time?

This is the power of frameworks. They help you write correct code even when you are sleepy. Even if you haven't learned much before, this way of thinking puts you at a higher level than others.

Teaching people to fish is better than giving them fish. Algorithms are not hard. Anyone can learn them well, as long as they want to. I hope you can develop a systematic way of thinking here, enjoy mastering algorithms, and not be controlled by them.