0698.深度优先搜索

A DFS problem from leetcode 698. Partition to K Equal Sum Subsets

I find my old version solution in 2018 invalid this try.
Then I look up some of most votes items and meet the same situation.
I get a dfs solution which is faster than the bit-mask method.
In the end, I think this problem should be Hard level because of the rigid time limit.

We use three trickes to meet the requirment:

1. end straight when there is no bucket can hold nums[index]
2. end straight when index arrive the length of nums without examination of cur_sum array
3. reversed sort array nums

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        target = sum(nums)
        if target % k != 0: return False
        target //= k
        cur = [0] * k; nums.sort( reverse = True)
        def foo( index):
            if index == len( nums): return True
            for i in range( k):
                if nums[index] + cur[i] <= target:
                    cur[i] += nums[index]
                    if foo( index + 1) == True: return True
                    cur[i] -= nums[index]
                if cur[i] == 0: break
            return False
        return foo( 0)

Thanks for your issue. I’ll list my thinking progress.

1. For the first tips:

Our target is to divide an array nums with size length to k different bucket with same sum.
If we could make it, there must be a bucket holding nums[index], and the bucket’s order doesn’t matter.

Inner the for i in range(k) loop, before the i-th loop, cur[i] which means the current sum of i-th bucket has two situations:

• cur[i] != 0
• cur[i] == 0: it means the i-th bucket is empty.
  However, there is an unspoken rules: cur[j] = 0 if j > i and cur[i] == 0. If after this step, the empty bucket i couldn’t hold nums[index], neither the later.

It’s an algorithm design paradigm named Branch and bound

2. For the second tips:

Lines 10 if nums[index] + cur[i] <= target ensure that any bucket’s sum cur[i] <= target

When we get the index == len( nums) for 0-index arrays, it means:

• any number from nums has been in a bucket
• cur[0] + cur[1] + ... + cur[k-1] = sum(nums) = k * target
• 0 <= cur[i] <= target, for i = 0, 1, 2, ..., k- 1

If there is a cur[i] not equals to target, sum( cur) must be less than k * target.

We use loop invariant to prove it.