是否和包含

有一個數組 : 3, 34, 4, 12, 5, 2

題目 : 是否有排列組合的和剛好等於 9 例如 : 4, 5 = 9 -> true 但 -1 沒有一個組合可以為他 -> false

思路 :

如上面 於 sub(arr[0~5], 9) 時 選擇是否要從 arr[5] 去做 sum 選擇 arr[5] 做, 下一個 -> sub(arr[0~4], 9 - arr[5]) 不選擇 arr[5] 做, 下一個 -> sub(arr[0~4], 9) 最後 or(選擇 arr[5], 不選 arr[5])

虛擬碼 :

//// 條件 :
// 發生如果 arr[n] 本身的值 > sum
if sum > 0 && arr[n] > sum :
    sub(arr[0~n], sum) = sub(arr[0 ~(n-1)], sum)
// 正常情況 
if sum > 0:
    sub(arr[0~n], sum) = or(sub(arr[0 ~ (n-1)], sum - arr[n]), sub(arr[0 ~ (n-1)], sum))

//// 終止 :
// 正常情況
if sum == 0:
    return true
// 剛好計算到只剩一筆 sub(arr[0], sum)
if len(arr) == 1:
    return arr[0] == sum

code (golang) common

import (
    "fmt"
)

var gWorkArray []int

func prepare(){
    gWorkArray= make([]int, 6)
    gWorkArray[0] = 3
    gWorkArray[1] = 34
    gWorkArray[2] = 4
    gWorkArray[3] = 12
    gWorkArray[4] = 5
    gWorkArray[5] = 2
}

code (golang) 遞迴 (result : true, true, true, false)

func recursive(array []int, sum int) bool{
    arrLen := len(array)
    lastIndex := arrLen - 1
    if sum == 0{
        return true
    }else if arrLen == 1{
        return array[0] == sum
    }else if array[lastIndex] > sum{
        return recursive(array[0: arrLen - 1], sum)
    }else{
        selection := recursive(array[0: arrLen - 1], sum - array[lastIndex])
        noSelection := recursive(array[0: arrLen - 1], sum)
        return selection || noSelection
    }
}

func main(){
    prepare()
    fmt.Println("recursive sum 10 result --> ", recursive(gWorkArray, 10))
    fmt.Println("recursive sum 11 result --> ", recursive(gWorkArray, 11))
    fmt.Println("recursive sum 12 result --> ", recursive(gWorkArray, 12))
    fmt.Println("recursive sum 13 result --> ", recursive(gWorkArray, 13))
}

動態規劃需使用 2 維陣列, 如下圖 (sum = 8)

條件 :

sum = 0 時都為 true, 如下圖

條件 :

len(arr) == 1 時, if sum == arr[n] return true else return false, 如下圖

剩餘的從二維 (1,1) -> (1,2) -> (1,3) 開始去判斷為 true or false 條件 :

if sum > 0 && arr[n] > sum :
    sub(arr[0~n], sum) = sub(arr[0 ~(n-1)], sum)
// 正常情況 
if sum > 0:
    sub(arr[0~n], sum) = or(sub(arr[0 ~ (n-1)], sum - arr[n]), sub(arr[0 ~ (n-1)], sum))

code (golang) 動態規劃 (result : true, true, true, false)

func createDpArray(sum int) [][]bool{
    // optArray[gWorkArray][sum]
    optArray := make([][]bool,len(gWorkArray))
    for i:= 0; i < len(gWorkArray); i++{
        optArray[i] = make([]bool, sum + 1)
    }
    return optArray
}

func dp(sum int) bool{
    dpArray := createDpArray(sum)
    // sum == 0, true
    for i:= 0; i < len(gWorkArray); i++{
        dpArray[i][0] = true
    }

    // gWorkArray's index == 0, sum = gWorkArray[0] = true, other false
    for i:= 0; i < (sum + 1); i++{
        dpArray[0][i] = false
    }
    dpArray[0][gWorkArray[0]] = gWorkArray[0] == sum

    // === other
    for arrayIndex := 1; arrayIndex < len(gWorkArray); arrayIndex++{
        for sumIndex :=1; sumIndex < (sum + 1); sumIndex++{
            if gWorkArray[arrayIndex] > sumIndex{
                dpArray[arrayIndex][sumIndex] = dpArray[arrayIndex - 1][sumIndex]
            }else{
                selection := dpArray[arrayIndex - 1][sumIndex - gWorkArray[arrayIndex]]
                noSelection := dpArray[arrayIndex - 1][sumIndex]
                dpArray[arrayIndex][sumIndex] = selection || noSelection
            }
        }
    }

    return dpArray[len(gWorkArray) - 1][sum]
}

func main(){
    prepare()
    fmt.Println("dp sum 10 result --> ", dp(10))
    fmt.Println("dp sum 11 result --> ", dp(11))
    fmt.Println("dp sum 12 result --> ", dp(12))
    fmt.Println("dp sum 13 result --> ", dp(13))
}