Partition Equal Subset Sum

1. Problem Description

Given a non-empty array containing only positive integers, determine whether the array can be partitioned into two subsets whose sums are equal.

2. Approach

1. Approach 1
   • DFS
   • Essentially the same as Combination Sum
   • The difference is that an element cannot be selected repeatedly
2. Approach 2
   • DFS + memoization

3. Implementation

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 + Memoization

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. References

• Understanding the 0-1 Knapsack Problem: Memoized Search, Dynamic Programming + Space Optimization - Partition Equal Subset Sum - LeetCode