刷leetcode时遇到好几个组合总和类题目,在这里汇总归纳一下
- leetcode算法题–组合总和 Ⅳ
- 零钱兑换 II
- leetcode算法题–组合总和
一般这类题目有两种做法,动态规划或者是dfs。一般如果题目只要求一个组合数,那么一般就使用动态规划做,因为题目会对时间复杂度会做一定限制,使用dfs一般过不了,如第1、2题。如果题目要求组合排列,那么可以使用dfs做,此时题目会对时间复杂度做一定放宽,如第3题。并且这类题目都是可以重复使用数,但是对不同顺序数字排列是否视为不同的组合将题目又分为两类,视为相同,如第2题;视为不同,如第1题。这导致了第1题和第2题的做法有细微不同,非常巧妙。
动态规划思路
先比较第1题和第2题的代码
// 组合总和IV
func combinationSum4(nums []int, target int) int {dp :=make([]int, target+1)dp[0] = 1for i := 1; i <= target; i ++ {for _, num := range nums {if num <= i {dp[i] += dp[i-num]} }}return dp[target]
}
// 零钱兑换II
func change(amount int, coins []int) int {dp := make([]int, amount+1)dp[0] = 1for _, coin := range coins { //每出现一个新的硬币刷新dpfor i := coin; i <= amount; i ++ {dp[i] += dp[i-coin]}}return dp[amount]
}
很容易发现,如果对不同顺序数字排列是否视为不同,则数组中数就不可以重复使用,于是放在外层循环,反之放在内层循环。
dfs思路
dfs思路其实也比较明显,比较值得注意的是这个idx的传入,可以让dfs不走回头路。
func combinationSum(candidates []int, target int) [][]int {res := make([][]int, 0)n := len(candidates)var dfs func(nums []int, target, idx int)dfs = func(nums []int, target, idx int) {if target == 0 {tmp := make([]int, len(nums)) copy(tmp, nums)res = append(res, tmp)return }for i := idx ; i < n; i ++ {c := candidates[i]if target - c >= 0{nums = append(nums, c)dfs(nums, target-c, i) nums = nums[:len(nums)-1] }} }dfs([]int{}, target, 0)return res
}