跳转至

LC416 - 分割等和子集

PartitionEqualSubsetSum.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package DP

//func canPartition(nums []int) bool {
//  size := len(nums)
//  sum := 0
//  for i := 0; i < size; i++ {
//      sum += nums[i]
//  }
//  if sum%2 != 0 {
//      return false
//  }
//  target := sum / 2
//  var f func(int, int) bool
//  f = func(index, rest int) bool {
//      if index == size {
//          return rest == 0
//      }
//      ret1 := f(index+1, rest)
//      ret2 := false
//      if rest >= nums[index] {
//          ret2 = f(index+1, rest-nums[index])
//      }
//      return ret1 || ret2
//  }
//  return f(0, target)
//}

func canPartition(nums []int) bool {
    size := len(nums)
    sum := 0
    for i := 0; i < size; i++ {
        sum += nums[i]
    }
    if sum%2 != 0 {
        return false
    }
    target := sum / 2
    dp := make([][]bool, size+1)
    for i := 0; i <= size; i++ {
        dp[i] = make([]bool, target+1)
    }
    dp[size][0] = true
    for i := size - 1; i >= 0; i-- {
        for j := 0; j <= target; j++ {
            dp[i][j] = dp[i+1][j]
            if j >= nums[i] {
                dp[i][j] = dp[i][j] || dp[i+1][j-nums[i]]
            }
        }
    }
    return dp[0][target]
}