416.md

Partition Equal Subset Sum

题目:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]
Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
 

Example 2:

Input: [1, 2, 3, 5]
Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

思路：

   回溯法。假设数组的和为a
   1. 如果a为奇数，返回false。(两个数组相同, 那么两个subset的和必然为偶数也就是说数组和为偶数才有解)
   2. 如果为偶数则使用回溯法。对于[1,2,3,4,5,6,7] 和的一半为14
   [1] [1,2],[1,2,3],[1,2,3,4](5,6,7都不行),回溯上一位[1,2,3],[1,2,3,5](6,7不行回溯),
   [1,2,3,6](7不行回溯),[1,2,4],[1,2,4,5],[1,2,4,6](7不行回溯)[1,2,4],[1,2,4,7] ok
   
   注意：
   1.有可能一直加到数组的最后面还是于一半。
   2.栈为空继续做pop操作的时候表示回溯已经全部试完，返回false
   3.排序int切片用sort.Ints(slice)
   4.剪枝操作：正常pop后会向后试下一位，在测试之前之前检测是否和pop位置的值相等，相等继续检测下一位，直到不相等位置再试。

代码：

func canPartition(nums []int) bool {
    tot := 0
    length := len(nums)
    for _, val := range nums {
        tot += val
    }
    if (tot & 1) == 1 {
        return false
    }
    half := tot/2
    sort.Ints(nums)
    stack, top, pop := make([]int, length-1), 0, 0
    tot = 0
    for cur:=0; cur < length; cur += 1 {
        tot += nums[cur]
        if tot == half {
            return true
        } else if tot < half && cur != length - 1 {
            stack[top] = cur
            top += 1
        } else {
            tot -= nums[cur]
            for {
                top -= 1
                if top == -1 {
                    return false
                }
                cur, pop = stack[top], stack[top]
                tot -= nums[pop]
                for cur + 1 < length && nums[pop] == nums[cur+1] {
                    cur += 1
                }
                if cur + 1 != length {
                    break
                }
            }
        }
    }
    return false
}