func LetterCombinations(digits string) []string {
	paths := []string{}
	if len(digits) == 0 {
		return paths
	}
	dict := []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	dfs(dict, digits, 0, nil, &paths)
	return paths
}
 
func dfs(dict []string, digits string, idx int, path []rune, paths *[]string) {
	if idx == len(digits) {
		*paths = append(*paths, string(path))
		return
	}

	for _, letter := range dict[digits[idx]-'2'] {
		path = append(path, letter)
		dfs(dict, digits, idx+1, path, paths)
		path = path[:len(path)-1]
	}
}

func KSumII(a []int, k int, target int) [][]int {
	// 这里需要sort(a)吗?不需要，本题无需按照字母序，也无重复
	// 排序所有字母，排序的意义:
	// 1.可以按照字母序得到结果
	// 2.相同的字母在一起，方便去重
	subsets := [][]int{}
	dfsKSumII(a, k, target, 0, nil, &subsets)
	return subsets
}

func dfsKSumII(a []int, k int, target int, idx int, subset []int, subsets *[][]int) {
	if k == 0 && target == 0 {
		// log.Println(subset)
		*subsets = append(*subsets, append([]int{}, subset...))
		return
	}

	if k == 0 || target <= 0 {
		return
	}

	for i := idx; i < len(a); i++ {
		// log.Printf("i = %d, a[i] = %d, k = %d, target = %d, idx = %d", i, a[i], k, target, idx)
		subset = append(subset, a[i])
		dfsKSumII(a, k-1, target-a[i], i+1, subset, subsets)
		subset = subset[:len(subset)-1]
	}
}

func CombinationSum(candidates []int, target int) [][]int {
	subsets := [][]int{}
	if len(candidates) == 0 {
		return subsets
	}
	dict := removeDuplicatesAndSort(candidates)
	dfsCombinationSum(dict, target, 0, nil, &subsets)
	return subsets
}

func dfsCombinationSum(dict []int, target int, idx int, subset []int, subsets *[][]int) {
	if target == 0 {
		*subsets = append(*subsets, append([]int{}, subset...))
	}
	for i := idx; i < len(dict); i++ {
		if target < dict[i] {
			break
		}
		subset = append(subset, dict[i])
		dfsCombinationSum(dict, target-dict[i], i, subset, subsets)
		subset = subset[:len(subset)-1]
	}
}

func removeDuplicatesAndSort(nums []int) []int {
	n := len(nums)
	if n == 0 {
		return nums
	}
	sort.Ints(nums)
	slow := 1
	for fast := 1; fast < n; fast++ {
		if nums[fast] != nums[fast-1] {
			nums[slow] = nums[fast]
			slow++
		}
	}
	return nums[:slow]
}

func StringPermutation(str string) []string {
	permutations := []string{}
	if str == "" {
		return permutations
	}
	chars := []rune(str)
	sort.Slice(chars, func(i, j int) bool {
		return chars[i] < chars[j]
	})

	visited := make([]bool, len(chars))
	stringPermutationDfs(chars, visited, []rune{}, &permutations)
	return permutations
}

func stringPermutationDfs(chars []rune, visited []bool, permutation []rune, permutations *[]string) {
	if len(permutation) == len(chars) {
		*permutations = append(*permutations, string(permutation))
	}

	for i, char := range chars {
		if visited[i] {
			continue
		}

		if i > 0 && char == chars[i-1] && !visited[i-1] {
			continue
		}

		visited[i] = true
		permutation = append(permutation, char)
		stringPermutationDfs(chars, visited, permutation, permutations)
		permutation = permutation[:len(permutation)-1]

		visited[i] = false
	}
}

func WordSearchII(board [][]byte, words []string) []string {
	var res []string
	if len(board) == 0 || len(board[0]) == 0 {
		return res
	}

	visited := make([][]bool, len(board))
	for i := range visited {
		visited[i] = make([]bool, len(board[0]))
	}
	wordSet := make(set)
	prefixSet := make(set)
	resSet := make(set)

	for _, word := range words {
		wordSet[word] = true
		for i := 0; i < len(word); i++ {
			prefixSet[string(word[:i+1])] = true
		}
	}

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			visited[i][j] = true
			wordSearchIIDfs(board, visited, i, j, string(board[i][j]), wordSet, prefixSet, resSet)
			visited[i][j] = false
		}
	}

	res = make([]string, 0, len(resSet))
	for k := range resSet {
		res = append(res, k)
	}
	return res
}

func wordSearchIIDfs(board [][]byte, visited [][]bool, x int, y int, word string, wordSet set, prefixSet set, resSet set) {
	if !prefixSet[word] {
		return
	}

	if wordSet[word] {
		resSet[word] = true
	}

	for i := 0; i < len(Directions); i++ {
		adjX := x + Directions[i].x
		adjY := y + Directions[i].y
		if !inside(board, adjX, adjY) || visited[adjX][adjY] {
			continue
		}
		visited[adjX][adjY] = true
		wordSearchIIDfs(board, visited, adjX, adjY, word+string(board[adjX][adjY]), wordSet, prefixSet, resSet)
		visited[adjX][adjY] = false
	}
}

func inside(board [][]byte, x, y int) bool {
	return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}