2021-08-09:给定一个有正、有负、有0的数组arr,给定一个整数k,返回arr的子集是否能累加出k。1)正常怎么做?2)如果arr中的数值很大,但是arr的长度不大,怎么做?
福大大 答案2021-08-09:
将数组划分成两部分,对左部分和右部分用动态规划。
代码用golang编写。代码如下:
package main import "fmt" func main() { ret := isSum4([]int{1, 2, 3}, 4) fmt.Println(ret) } // arr中的值可能为正,可能为负,可能为0 // 自由选择arr中的数字,能不能累加得到sum // 分治的方法 // 如果arr中的数值特别大,动态规划方法依然会很慢 // 此时如果arr的数字个数不算多(40以内),哪怕其中的数值很大,分治的方法也将是最优解 func isSum4(arr []int, sum int) bool { if sum == 0 { return true } if len(arr) == 0 { return false } if len(arr) == 1 { return arr[0] == sum } N := len(arr) mid := N >> 1 leftSum := make(map[int]struct{}) rightSum := make(map[int]struct{}) // 0...mid-1 process4(arr, 0, mid, 0, leftSum) // mid..N-1 process4(arr, mid, N, 0, rightSum) // 单独查看,只使用左部分,能不能搞出sum // 单独查看,只使用右部分,能不能搞出sum // 左+右,联合能不能搞出sum // 左部分搞出所有累加和的时候,包含左部分一个数也没有,这种情况的,leftsum表里,0 // 17 17 for l, _ := range leftSum { if _, ok := rightSum[sum-l]; ok { return true } } return false } // arr[0...i-1]决定已经做完了!形成的累加和是pre // arr[i...end - 1] end(终止) 所有数字随意选择, // arr[0...end-1]所有可能的累加和存到ans里去 func process4(arr []int, i int, end int, pre int, ans map[int]struct{}) { if i == end { ans[pre] = struct{}{} } else { process4(arr, i+1, end, pre, ans) process4(arr, i+1, end, pre+arr[i], ans) } }
执行结果如下: