3.7 DFS

1. What Is DFS

• Depth-first search, suitable for strings, arrays, and trees, and often used together with Backtracking

2. Strings

2.1. Permutations

• Input a string and output all its permutations
• Analysis: use a tree
  • 

2.1.1. Classic Approach

func dfs1(str string) {
	allPaths := make([]string, 0)
	path := make([]rune, 0)
	visited := make([]bool, len([]rune(str)), len([]rune(str)))
	dfsRecur([]rune(str), 0, len([]rune(str)), &path, &allPaths, visited)
	fmt.Println(allPaths)
}

func dfsRecur(runes []rune, index int, length int, path *[]rune, allPaths *[]string, visited []bool) {
	// Termination condition
	if index == length {
		res := string(*path)
		*allPaths = append(*allPaths, res)
		return
	}

	// Traverse candidate nodes
	for i := 0; i < length; i++ {
		// Visit only nodes that have not been visited
		if !visited[i] {
			visited[i] = true
			*path = append(*path, runes[i])

			dfsRecur(runes, index+1, length, path, allPaths, visited)

			// Backtrack
			visited[i] = false
			*path = (*path)[:len(*path)-1]
		}
	}
}

2.1.2. Improved Version

func dfs3(str string) {
	allPaths := make([]string, 0)
	dfsRecur3([]rune(str), 0, len([]rune(str)), &allPaths)
	fmt.Println(allPaths)
}

func dfsRecur3(runes []rune, index int, length int, allPaths *[]string) {
	// Termination condition
	if index == length {
		res := string(runes)
		*allPaths = append(*allPaths, res)
		return
	}

	// Traverse candidate nodes
	for i := index; i < length; i++ {

		swap(runes, i, index)

		dfsRecur3(runes, index+1, length, allPaths)

		swap(runes, i, index)

	}
}

func swap(runes []rune, i int, j int) {
	runes[i], runes[j] = runes[j], runes[i]
}

2.2. Combinations

func dfs2(str string) {
	allPaths := make([]string, 0)
	path := make([]rune, 0)
	dfsRecur2([]rune(str), 0, len([]rune(str)), &path, &allPaths)
	fmt.Println(allPaths)
}

func dfsRecur2(runes []rune, index int, length int, path *[]rune, allPaths *[]string) {
	// Termination condition
	res := string(*path)
	*allPaths = append(*allPaths, res)

	// Traverse candidate nodes
	for i := index; i < length; i++ {
		// Visit the candidate
		*path = append(*path, runes[i])

		dfsRecur2(runes, i+1, length, path, allPaths)

		*path = (*path)[:len(*path)-1]

	}
}

• Subsets

3. Arrays

3.1. Combination Sum

• Combination Sum