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)
    }
}

执行结果如下:
在这里插入图片描述


左神java代码