Backtracking can also help us to get all subsets of a given slice. If Combination and Partitioning problems can be converted to get root-to-leaf paths during a tree DFS traversal, Subsets can be treated as getting all root-to-node paths during a tree DFS traversal.

Partitioning is another classical problem which can be solved with backtracking algorithm.

131. Palindrome Partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func partition(s string) [][]string {
    result := [][]string{}
    path := []string{}
    length := len(s)
    isParlindrom := func(s string) bool {
        for i, j := 0, len(s) - 1; i < j; i, j := i + 1, j - 1 {
            if s[i] != s[j] {
                return false
            }
        }
        return true
    }
    var backtracking func(int)
    backtracking = func(index int) {
        if index == length {
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            return
        }
        for i := index; i < length; i++ {
            if isParlindrom(s[index:i + 1]) {
                path = append(path, s[index: i + 1])
                backtracking(i + 1)
                path = path[:len(path) - 1]
            }
        }
    }
    backtracking(0)
    return result
}

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree). Usually we can consider backtracking as DFS recursively traversal.

108. Convert Sorted Array to Binary Search Tree

Highed balanced means left nodes and right nodes have the minimized same size difference.

700. Search in a Binary Search Tree

Naive BST query.

Bluetooth technology has been widely used in various devices, such as earphones, speakers, smart watches and so on. One of the important applications is Bluetooth positioning technology, which can determine the distance between devices by measuring the strength of Bluetooth signals. This method of distance estimation based on signal strength is called RSSI (Received Signal Strength Indication) ranging. In this article, we will discuss the principle, implementation, and related application scenarios of RSSI ranging.

1008. Construct Binary Search Tree from Preorder Traversal

Based on the preorder traversal definition for a BST, the first element in the slice is always coming from the root node, we can split the rest elements into two parts from the element which is no less than the root node for child nodes.

101. Symmetric Tree

a. DFS solution

Fingerprint-based Bluetooth Localization (Fingerprint-based Bluetooth Localization) is a commonly used indoor positioning algorithm. Its basic principle is to establish a fingerprint database by recording the Bluetooth signal strength values at different locations, and then according to the Bluetooth signal strength values received by the device, Match the most similar fingerprints to determine where the device is located.

102. Binary Tree Level Order Traversal

a. BFS solution