分割等和子集

1. 题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

2. 思路

1. 思路一
   • DFS
   • 本质上和组合总和.md一样
   • 区别在于不能重复选取
2. 思路二
   • DFS+缓存

3. 实现

3.1. DFS

func canPartition(nums []int) bool {
    s := sum(nums)
    if s % 2 ==1 {return false}
    // memo := make(map[int]bool, 0)
    return canPartitionDFS(nums, 0, s/2)
}

func canPartitionDFS(nums []int, index, target int) bool {
    if index >= len(nums) || target < 0 {
        return false
    }
    if nums[index] == target {
        return true
    }

    selectedRes := canPartitionDFS(nums, index+1, target-nums[index])
    if selectedRes {
        return true
    }
    notSelectedRes := canPartitionDFS(nums, index+1, target)
    if notSelectedRes {
        return true
    }
    return false
}

func sum(nums []int) int {
    res := 0
    for _, num := range nums {
        res += num
    }
    return res
}

3.2. DFS+缓存

func canPartition(nums []int) bool {
    s := sum(nums)
    if s % 2 ==1 {return false}

    memo := make(map[string]bool, 0)
    return canPartitionDFS(nums, 0, s/2, memo)
}

func canPartitionDFS(nums []int, index, target int, memo map[string]bool) bool {
    key := buildKey(target, index)
    if res ,ok := memo[key]; ok {
        return res
    }
    if index >= len(nums) || target < 0 {
        return false
    }
    if nums[index] == target {
        memo[key] = true
        return true
    }

    selectedRes := canPartitionDFS(nums, index+1, target-nums[index], memo)
    if selectedRes {
        memo[key] = true
        return true
    }
    notSelectedRes := canPartitionDFS(nums, index+1, target, memo)
    if notSelectedRes {
        memo[key] = true
        return true
    }
    memo[key] = false
    return false
}

func buildKey(target int, index int) string {
    return fmt.Sprintf("%d_%d", target, index)
}

func sum(nums []int) int {
    res := 0
    for _, num := range nums {
        res += num
    }
    return res
}

4. 参考

• 『 一文搞懂 0-1背包问题 』记忆化搜索、动态规划 + 空间优化 - 分割等和子集 - 力扣（LeetCode）