文章 212
评论 2
浏览 124959
Backtracking - 93. Restore IP Addresses

Backtracking - 93. Restore IP Addresses

93. Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 思路: 题目意思是给一个只包含数字的字符串给出所有合法ip地址的组合。一看就是很典型使用回溯来枚举的题目,使用ip地址每一位值只能是[0, 255]之间的值来剪枝。同时每一位可能有1位或者两位或者三位数字,这样来分别dfs递归求解。 代码: go: func restoreIpAddresses(s string) []string { var res []string if s == "" || len(s) < 4 || len(s) > 12 { return res } dfs(&res, s, "", 0) return res } ....

Backtracking - 17. Letter Combinations of a Phone Number

Backtracking - 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 思....

Backtracking - 47. Permutations II

Backtracking - 47. Permutations II

47. Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 思路: 和46题差别在于数字有重复,需要返回unique的组合,组合问题,只要有重复,通解思路都是先先排序,剩下的就基本和46题一样,还需判断一个数是否被用过来剪枝。 代码: go: func permuteUnique(nums []int) [][]int { sort.Ints(nums) return permute(nums) } func permute(nums []int) [][]int { var res [][]int dfs(0, nums, &res) return res } func dfs(start int, nums []int, res *[][]int){ if....

Backtracking - 46. Permutations

Backtracking - 46. Permutations

46. Permutations Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 思路: 题目意思很简单就是求出一个数组的排列组合,思路就是使用回溯来做。 代码: go: func permute(nums []int) [][]int { var res [][]int dfs(0, nums, &res) return res } func dfs(start int, nums []int, res *[][]int){ if start == len(nums) { *res = append(*res, append([]int{}, nums...)) return } for i := start; i < len(nums); i++ { num....

Backtracking - 216. Combination Sum III

Backtracking - 216. Combination Sum III

216. Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] 思路: 这一题是组合系列的变形题,要求用k个1-9的数组组合出n值,采用回溯来做,使用组合的个数为k个和为n来剪....

Backtracking - 40. Combination Sum II

Backtracking - 40. Combination Sum II

40. Combination Sum II Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8,....

Backtracking - 39. Combination Sum

Backtracking - 39. Combination Sum

39. Combination Sum Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candida....

Nothing just happens, it's all part of a plan.