Dfs

func combine(n int, k int) (ans [][]int) {
    path := []int{}
    var dfs func(int)
    dfs = func(cur int) {
        if len(path) == k {
            ans = append(ans, append([]int{}, path...))
            return
        }
		// 剪枝
        d := k - len(path)
        if n-cur+1 < d {
            return
        }
        for i := cur; i <= n; i++ {
            path = append(path, i)
            dfs(i+1)
            path = path[:len(path)-1]
        }
    }
    dfs(1)
    return
}

func combinationSum3(k int, n int) (ans [][]int) {
	var com []int
	var dfs func(int, int)
	dfs = func(cur, sum int) {
		if sum > n {
			return
		}
		if len(com) == k {
			if sum == n {
				ans = append(ans, append([]int{}, com...))
			}
			return
		}

		// 还有 k-len(com) 个元素要取, 如果
		for i := cur; i <= 9-(k-len(com))+1; i++ {
			sum += i
			com = append(com, i)
			dfs(i+1, sum)
			sum -= i
			com = com[:len(com)-1]
		}
	}

	dfs(1, 0)
	return
}

func letterCombinations(digits string) (ans []string) {
	if len(digits) == 0 {
		return
	}
	var path string
	var dfs func(int)
	dfs = func(cur int) {
		if cur == len(digits) {
			ans = append(ans, path)
			return
		}

		var ss []string
		switch digits[cur] {
		case '2':
			ss = []string{"a", "b", "c"}
		case '3':
			ss = []string{"d", "e", "f"}
		case '4':
			ss = []string{"g", "h", "i"}
		case '5':
			ss = []string{"j", "k", "l"}
		case '6':
			ss = []string{"m", "n", "o"}
		case '7':
			ss = []string{"p", "q", "r", "s"}
		case '8':
			ss = []string{"t", "u", "v"}
		case '9':
			ss = []string{"w", "x", "y", "z"}
		}
		for _, s := range ss {
			path += s
			dfs(cur + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return
}

func combinationSum(candidates []int, target int) (ans [][]int) {
	var path []int
	var dfs func(int, int)
	dfs = func(start, sum int) {
		if sum >= target {
			if sum == target {
				ans = append(ans, append([]int{}, path...))
			}
			return
		}
		// 从 start 开始, 因为可以重复取元素, 但是为了避免集合重复
		// 所以不能再取 i < start 的了
		for i := start; i < len(candidates); i++ {
			path = append(path, candidates[i])
			sum += candidates[i]
			dfs(i, sum)
			path = path[:len(path)-1]
			sum -= candidates[i]
		}
	}
	dfs(0, 0)
	return
}

func combinationSum2(candidates []int, target int) (ans [][]int) {
	// 排序, 使得相同值的元素排列在一起
	sort.Ints(candidates)
	// 这个变量帮助去判断在同一层级下, 是否有选取到和前面相同的元素
	used := make([]bool, len(candidates))
	var path []int
	var dfs func(int, int)
	dfs = func(start, sum int) {
		if sum >= target {
			if sum == target {
				ans = append(ans, append([]int{}, path...))
			}
			return
		}
		for i := start; i < len(candidates); i++ {
			// 如果当前选取的元素和数组中的上一个元素的值相同,
			// 那么, 假设当前元素与数组中的上一个元素都为 a
			// 并且!!!⚠️⚠️⚠️
			// 在 used 数组中, 数组的上一个元素并未被选取, 说明当前该元素并非在一个分支下
			// 并非在 dfs 递归的过程中被选取, 而是在 for 循环中被选取
			if i > 0 && candidates[i-1] == candidates[i] && !used[i-1] {
				continue
			}
			path = append(path, candidates[i])
			used[i] = true
			sum += candidates[i]
			dfs(i+1, sum)
			path = path[:len(path)-1]
			used[i] = false
			sum -= candidates[i]
		}
	}
	dfs(0, 0)
	return
}

            【 1  1  1  3 】                 
               /      |                          
         1√   /    1× |                          
             /        |                          
            v         v                          
       【 1 1 3 】  【 1 3 】                        
         /  \                                     
    1√  /    \  1×                                  
       /      \                                   
      v        v                                  
  【 1 3 】   【 3 】

func solveNQueens(n int) (ans [][]string) {
	var path []int
	queen := make([]bool, n)
	queenLegal := func() bool {
		for i, p := range path {
			for j := i + 1; j < len(path); j++ {
				if j-i == path[j]-p {
					return false
				}
				if j-i == p-path[j] {
					return false
				}
			}
		}
		return true
	}
	var dfs func()
	dfs = func() {
		if len(path) == n {
			if queenLegal() {
				board := make([]string, n)
				for i, c := range path {
					board[i] = strings.Repeat(".", c) + "Q" + strings.Repeat(".", n-c-1)
				}
				ans = append(ans, board)
			}
			return
		}

		for i := 0; i < n; i++ {
			if queen[i] {
				continue
			}
			queen[i] = true
			path = append(path, i)
			dfs()
			queen[i] = false
			path = path[:len(path)-1]
		}
	}
	dfs()
	return
}

func partition(s string) (ans [][]string) {
	var path []string

	isPalid := func(i, j int) bool {
		for i < j {
			if s[i] != s[j] {
				return false
			}
			i++
			j--
		}
		return true
	}

	var dfs func(int)
	dfs = func(start int) {
		if start >= len(s) {
			ans = append(ans, append([]string{}, path...))
			return
		}

		for j := start; j < len(s); j++ {
			if !isPalid(start, j) {
				continue
			}
			path = append(path, s[start:j+1])
			dfs(j + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return
}