Question

698. Partition to K Equal Sum Subsets

中文文档

Description

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

 

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

 

Constraints:

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 104
• The frequency of each element is in the range [1, 4].

Solutions

Solution 1

class Solution:
  def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
    def dfs(i):
      if i == len(nums):
        return True
      for j in range(k):
        if j and cur[j] == cur[j - 1]:
          continue
        cur[j] += nums[i]
        if cur[j] <= s and dfs(i + 1):
          return True
        cur[j] -= nums[i]
      return False

    s, mod = divmod(sum(nums), k)
    if mod:
      return False
    cur = [0] * k
    nums.sort(reverse=True)
    return dfs(0)

class Solution {
  private int[] nums;
  private int[] cur;
  private int s;

  public boolean canPartitionKSubsets(int[] nums, int k) {
    for (int v : nums) {
      s += v;
    }
    if (s % k != 0) {
      return false;
    }
    s /= k;
    cur = new int[k];
    Arrays.sort(nums);
    this.nums = nums;
    return dfs(nums.length - 1);
  }

  private boolean dfs(int i) {
    if (i < 0) {
      return true;
    }
    for (int j = 0; j < cur.length; ++j) {
      if (j > 0 && cur[j] == cur[j - 1]) {
        continue;
      }
      cur[j] += nums[i];
      if (cur[j] <= s && dfs(i - 1)) {
        return true;
      }
      cur[j] -= nums[i];
    }
    return false;
  }
}

class Solution {
public:
  bool canPartitionKSubsets(vector<int>& nums, int k) {
    int s = accumulate(nums.begin(), nums.end(), 0);
    if (s % k) {
      return false;
    }
    s /= k;
    int n = nums.size();
    vector<int> cur(k);
    function<bool(int)> dfs;
    dfs = [&](int i) {
      if (i == n) {
        return true;
      }
      for (int j = 0; j < k; ++j) {
        if (j && cur[j] == cur[j - 1]) {
          continue;
        }
        cur[j] += nums[i];
        if (cur[j] <= s && dfs(i + 1)) {
          return true;
        }
        cur[j] -= nums[i];
      }
      return false;
    };
    sort(nums.begin(), nums.end(), greater<int>());
    return dfs(0);
  }
};

func canPartitionKSubsets(nums []int, k int) bool {
  s := 0
  for _, v := range nums {
    s += v
  }
  if s%k != 0 {
    return false
  }
  s /= k
  cur := make([]int, k)
  n := len(nums)

  var dfs func(int) bool
  dfs = func(i int) bool {
    if i == n {
      return true
    }
    for j := 0; j < k; j++ {
      if j > 0 && cur[j] == cur[j-1] {
        continue
      }
      cur[j] += nums[i]
      if cur[j] <= s && dfs(i+1) {
        return true
      }
      cur[j] -= nums[i]
    }
    return false
  }

  sort.Sort(sort.Reverse(sort.IntSlice(nums)))
  return dfs(0)
}

function canPartitionKSubsets(nums: number[], k: number): boolean {
  let s = nums.reduce((a, b) => a + b);
  if (s % k !== 0) {
    return false;
  }
  s /= k;
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const f: boolean[] = new Array(1 << n).fill(false);
  f[0] = true;
  const cur: number[] = new Array(n).fill(0);
  for (let i = 0; i < 1 << n; ++i) {
    if (!f[i]) {
      continue;
    }
    for (let j = 0; j < n; ++j) {
      if (cur[i] + nums[j] > s) {
        break;
      }
      if (((i >> j) & 1) === 0) {
        f[i | (1 << j)] = true;
        cur[i | (1 << j)] = (cur[i] + nums[j]) % s;
      }
    }
  }
  return f[(1 << n) - 1];
}

Solution 2

class Solution:
  def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
    @cache
    def dfs(state, t):
      if state == mask:
        return True
      for i, v in enumerate(nums):
        if (state >> i) & 1:
          continue
        if t + v > s:
          break
        if dfs(state | 1 << i, (t + v) % s):
          return True
      return False

    s, mod = divmod(sum(nums), k)
    if mod:
      return False
    nums.sort()
    mask = (1 << len(nums)) - 1
    return dfs(0, 0)

class Solution {
  private int[] f;
  private int[] nums;
  private int n;
  private int s;

  public boolean canPartitionKSubsets(int[] nums, int k) {
    for (int v : nums) {
      s += v;
    }
    if (s % k != 0) {
      return false;
    }
    s /= k;
    Arrays.sort(nums);
    this.nums = nums;
    n = nums.length;
    f = new int[1 << n];
    return dfs(0, 0);
  }

  private boolean dfs(int state, int t) {
    if (state == (1 << n) - 1) {
      return true;
    }
    if (f[state] != 0) {
      return f[state] == 1;
    }
    for (int i = 0; i < n; ++i) {
      if (((state >> i) & 1) == 1) {
        continue;
      }
      if (t + nums[i] > s) {
        break;
      }
      if (dfs(state | 1 << i, (t + nums[i]) % s)) {
        f[state] = 1;
        return true;
      }
    }
    f[state] = -1;
    return false;
  }
}

class Solution {
public:
  bool canPartitionKSubsets(vector<int>& nums, int k) {
    int s = accumulate(nums.begin(), nums.end(), 0);
    if (s % k) {
      return false;
    }
    s /= k;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int mask = (1 << n) - 1;
    vector<int> f(1 << n);
    function<bool(int, int)> dfs;
    dfs = [&](int state, int t) {
      if (state == mask) {
        return true;
      }
      if (f[state]) {
        return f[state] == 1;
      }
      for (int i = 0; i < n; ++i) {
        if (state >> i & 1) {
          continue;
        }
        if (t + nums[i] > s) {
          break;
        }
        if (dfs(state | 1 << i, (t + nums[i]) % s)) {
          f[state] = 1;
          return true;
        }
      }
      f[state] = -1;
      return false;
    };
    return dfs(0, 0);
  }
};

func canPartitionKSubsets(nums []int, k int) bool {
  s := 0
  for _, v := range nums {
    s += v
  }
  if s%k != 0 {
    return false
  }
  s /= k
  n := len(nums)
  f := make([]int, 1<<n)
  mask := (1 << n) - 1

  var dfs func(int, int) bool
  dfs = func(state, t int) bool {
    if state == mask {
      return true
    }
    if f[state] != 0 {
      return f[state] == 1
    }
    for i, v := range nums {
      if (state >> i & 1) == 1 {
        continue
      }
      if t+v > s {
        break
      }
      if dfs(state|1<<i, (t+v)%s) {
        f[state] = 1
        return true
      }
    }
    f[state] = -1
    return false
  }

  sort.Ints(nums)
  return dfs(0, 0)
}

Solution 3

class Solution:
  def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
    s = sum(nums)
    if s % k:
      return False
    s //= k
    nums.sort()
    n = len(nums)
    f = [False] * (1 << n)
    cur = [0] * (1 << n)
    f[0] = True
    for i in range(1 << n):
      if not f[i]:
        continue
      for j in range(n):
        if cur[i] + nums[j] > s:
          break
        if (i >> j & 1) == 0:
          if not f[i | 1 << j]:
            cur[i | 1 << j] = (cur[i] + nums[j]) % s
            f[i | 1 << j] = True
    return f[-1]

class Solution {
  public boolean canPartitionKSubsets(int[] nums, int k) {
    int s = 0;
    for (int x : nums) {
      s += x;
    }
    if (s % k != 0) {
      return false;
    }
    s /= k;
    Arrays.sort(nums);
    int n = nums.length;
    boolean[] f = new boolean[1 << n];
    f[0] = true;
    int[] cur = new int[1 << n];
    for (int i = 0; i < 1 << n; ++i) {
      if (!f[i]) {
        continue;
      }
      for (int j = 0; j < n; ++j) {
        if (cur[i] + nums[j] > s) {
          break;
        }
        if ((i >> j & 1) == 0) {
          cur[i | 1 << j] = (cur[i] + nums[j]) % s;
          f[i | 1 << j] = true;
        }
      }
    }
    return f[(1 << n) - 1];
  }
}

class Solution {
public:
  bool canPartitionKSubsets(vector<int>& nums, int k) {
    int s = accumulate(nums.begin(), nums.end(), 0);
    if (s % k) {
      return false;
    }
    s /= k;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    bool f[1 << n];
    int cur[1 << n];
    memset(f, false, sizeof(f));
    memset(cur, 0, sizeof(cur));
    f[0] = 1;
    for (int i = 0; i < 1 << n; ++i) {
      if (!f[i]) {
        continue;
      }
      for (int j = 0; j < n; ++j) {
        if (cur[i] + nums[j] > s) {
          break;
        }
        if ((i >> j & 1) == 0) {
          f[i | 1 << j] = true;
          cur[i | 1 << j] = (cur[i] + nums[j]) % s;
        }
      }
    }
    return f[(1 << n) - 1];
  }
};

func canPartitionKSubsets(nums []int, k int) bool {
  s := 0
  for _, x := range nums {
    s += x
  }
  if s%k != 0 {
    return false
  }
  s /= k
  sort.Ints(nums)
  n := len(nums)
  f := make([]bool, 1<<n)
  cur := make([]int, 1<<n)
  f[0] = true
  for i := 0; i < 1<<n; i++ {
    if !f[i] {
      continue
    }
    for j := 0; j < n; j++ {
      if cur[i]+nums[j] > s {
        break
      }
      if i>>j&1 == 0 {
        f[i|1<<j] = true
        cur[i|1<<j] = (cur[i] + nums[j]) % s
      }
    }
  }
  return f[(1<<n)-1]
}