leetcode-go/medium/416.partition-equal-subset-sum.go

type ints []int

func (is ints) Len() int           { return len(is) }
func (is ints) Less(i, j int) bool { return is[j] < is[i] }
func (is ints) Swap(i, j int)      { is[i], is[j] = is[j], is[i] }

func canPartition(nums []int) (ans bool) {
	sum := 0
	for _, i := range nums {
		sum += i
	}
	if sum&1 == 1 {
		return false
	}
	sort.Sort(ints(nums))
	dfs(nums, len(nums), sum/2, 0, 0, 0, &ans)
	return
}

func dfs(nums []int, n, sum, i, p1, p2 int, ans *bool) {
	if *ans == true || sum < p1 || sum < p2 {
		return
	} else if i == n {
		*ans = p1 == p2
		return
	}
	dfs(nums, n, sum, i+1, p1+nums[i], p2, ans)
	dfs(nums, n, sum, i+1, p1, p2+nums[i], ans)
}