698. Divided into k equal subsets

The title

Given an integer array nums and a positive integer k, find out if it is possible to divide the array into k non-empty subsets whose summation is all equal.

Example 1

Input: nums = [4, 3, 2,3, 5, 2, 1], k = 4 Output: True Description: It is possible to divide it into 4 subsets (5), (1,4), (2,3), (2,3) equal to the sum.Copy the code

Example 2

Input: nums = [1,2,3,4], k = 3 output: falseCopy the code

prompt

  • 1 <= k <= len(nums) <= 16
  • 0 < nums[i] < 10000
  • The frequency of each element is in[1, 4]Within the scope of

Answer key

Recursion plus backtracking

Assumptions:

  • The array length is len
  • The array sum is total

So:

  • The sum of array elements must be divisible by KKK, otherwise it must return falseFalse directly
  • If it can be bisected, the sum of each non-empty subset target=total/ktarget =total/ktarget =total/k
  • Create a bucket of length KKK with the initial value set to 000
  • recursive

recursive

The array is enumerated from left to right, and the first bucket is filled to targettargettarget first. If the entire array cannot be enumerated, bucket 000 is filled to targettargettarget. We can end the recursion because none of the first buckets satisfy targettargettarget; There’s no point in filling the next bucket

If bucket 0 can be filled, continue to fill bucket 1 until bucket K is full. Returns true

Edit the code as follows:

var canPartitionKSubsets = function (nums, k) {
  const total = nums.reduce((a, b) = > a + b)
  if(total % k ! = =0) return false
  const target = total / k
  const list = Array(k).fill(0)
  const len = nums.length
  return dfs(0)
  function dfs(index) {
    if (index === len) return true
    for (let i = 0; i < k; i++) {
      if (list[i] + nums[index] <= target) {
        list[i] += nums[index]
        if (dfs(index + 1)) return true
        list[i] -= nums[index]
      }
      if (list[i] === 0 || list[i] + nums[index] === target) break
    }
    return false}}Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section