leetcode-go/medium/698.partition-to-k-equal-sum-subsets.go

type none struct{}

func canPartitionKSubsets(nums []int, k int) bool {
	sum := 0
	for _, i := range nums {
		sum += i
	}
	if sum%k != 0 {
		return false
	}
	sum /= k
	sort.Sort(sort.Reverse(sort.IntSlice(nums))) // Sort the nums to avoid TLE (or use memorized search)
	return dfs(nums, k, sum, 0, 0)
}

func dfs(nums []int, k, sum, cur, set int) bool {
	if k == 0 {
		return set == 1<<uint(len(nums))-1
	}
	for i := range nums {
		if set>>uint(i)&1 == 1 {
			continue
		}
		t := cur + nums[i]
		if sum < t {
			break
		}
		nset := set | (1 << uint(i))
		if t < sum {
			if dfs(nums, k, sum, t, nset) {
				return true
			}
		} else if dfs(nums, k-1, sum, 0, nset) {
			return true
		}
	}
	return false
}