Partition to k equal sum subsets

Array Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask

38.4% acceptance

Feb 20, 2026

7525

553

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

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_partition_k_subsets(mut nums: Vec<i32>, k: i32) -> bool {
    let total: i32 = nums.iter().sum();
    if total % k != 0 { return false; }
    let target = total / k;
    if nums.iter().any(|&x| x > target) { return false; }
    nums.sort_unstable_by(|a, b| b.cmp(a));
    let k = k as usize;
    let mut buckets = vec![0i32; k];
    Self::backtrack(&nums, &mut buckets, 0, target)
  }

  fn backtrack(nums: &[i32], buckets: &mut Vec<i32>, idx: usize, target: i32) -> bool {
    if idx == nums.len() {
      return buckets.iter().all(|&b| b == target);
    }
    let mut seen = std::collections::HashSet::new();
    for i in 0..buckets.len() {
      if seen.contains(&buckets[i]) { continue; }
      if buckets[i] + nums[idx] <= target {
        seen.insert(buckets[i]);
        buckets[i] += nums[idx];
        if Self::backtrack(nums, buckets, idx + 1, target) {
          return true;
        }
        buckets[i] -= nums[idx];
      }
    }
    false
  }
}