1. 組合總和

var (path []intres  [][]int
)func combinationSum(candidates []int, target int) [][]int {path = make([]int, 0)res = make([][]int, 0)dfs(candidates,target,0,0)return res
}func dfs(candidates []int, target int,tempTarget int,start int)  {if tempTarget>target{return}if tempTarget==target{temp := make([]int,len(path))copy(temp,path)res = append(res, temp)return}for i:=start;i<len(candidates);i++{path = append(path, candidates[i])dfs(candidates,target,tempTarget+candidates[i],i)path = path[:len(path)-1]}
}

2. 組合總和2

需要先對候選人進行一個排序

2.1 使用used數組

var (res [][]intpath  []intused  []bool
)
func combinationSum2(candidates []int, target int) [][]int {res, path = make([][]int, 0), make([]int, 0, len(candidates))used = make([]bool, len(candidates))sort.Ints(candidates)   // 排序，為剪枝做準備dfs(candidates, 0, target)return res
}func dfs(candidates []int, start int, target int) {if target == 0 {   // target 不斷減小，如果為0說明達到了目標值tmp := make([]int, len(path))copy(tmp, path)res = append(res, tmp)return}for i := start; i < len(candidates); i++ {if candidates[i] > target {  // 剪枝，提前返回break}// used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過// used[i - 1] == false，說明同一樹層candidates[i - 1]使用過if i > 0 && candidates[i] == candidates[i-1]  && used[i-1] == false { continue}path = append(path, candidates[i])used[i] = truedfs(candidates, i+1, target - candidates[i])used[i] = falsepath = path[:len(path) - 1]}
}

2.2 不使用used數組

var (res [][]intpath  []int
)
func combinationSum2(candidates []int, target int) [][]int {res, path = make([][]int, 0), make([]int, 0, len(candidates))sort.Ints(candidates)   // 排序，為剪枝做準備dfs(candidates, 0, target)return res
}func dfs(candidates []int, start int, target int) {if target == 0 {   // target 不斷減小，如果為0說明達到了目標值tmp := make([]int, len(path))copy(tmp, path)res = append(res, tmp)return}for i := start; i < len(candidates); i++ {if candidates[i] > target {  // 剪枝，提前返回break}// i != start 限制了這不對深度遍歷到達的此值去重if i != start && candidates[i] == candidates[i-1] { // 去重continue}path = append(path, candidates[i])dfs(candidates, i+1, target - candidates[i])path = path[:len(path) - 1]}
}

3. 分割回文串

var (path []stringres  [][]string
)func partition(s string) [][]string {path = make([]string, 0)res = make([][]string, 0)dfs(s,0)return res
}func dfs(s string, start int) {if len(s) == start { //表明找到了一個切割方案temp := make([]string, len(path))copy(temp, path)res = append(res, temp)}for i := start; i < len(s); i++ {if isPalindrome(s[start:i+1]){//表名當前是一個回文串path = append(path, s[start:i+1])dfs(s,i+1)path = path[:len(path)-1]}}
}func isPalindrome(s string) bool {for i:=0;i<len(s)/2;i++{if s[i]!=s[len(s)-i-1]{return false}}return true
}

4. 復原IP地址

var (path []stringres  []string
)func restoreIpAddresses(s string) []string {path = make([]string, 0)res = make([]string, 0)dfs(s, 0, 4)return res
}func dfs(s string, start int, remain int) {if remain == 0 && start == len(s) { //表明找到了一個切割方案temp := path[0]for i := 1; i < len(path); i++ {temp = temp + "." + path[i]}res = append(res, temp)}for i := start; i < start+3 && i < len(s); i++ {if isValidNumber(s[start : i+1]) {//表名當前是一個回文串path = append(path, s[start:i+1])dfs(s, i+1, remain-1)path = path[:len(path)-1]}}
}func isValidNumber(s string) bool {//前導零判斷if len(s) > 1 && s[0] == '0' {return false}//判斷數字大小是否在小于255num, _ := strconv.Atoi(s)if num > 255 {return false}return true
}

5. 子集問題

var (path   []intres  [][]int
)
func subsets(nums []int) [][]int {res, path = make([][]int, 0), make([]int, 0, len(nums))dfs(nums, 0)return res
}
func dfs(nums []int, start int) {tmp := make([]int, len(path))copy(tmp, path)res = append(res, tmp)for i := start; i < len(nums); i++ {path = append(path, nums[i])dfs(nums, i+1)path = path[:len(path)-1]}
}