Given an array of integers nums and a positive integer k, find whether it's 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's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:
1 <= k <= len(nums) <= 16.0 < nums[i] < 10000.struct Solution;
impl Solution {
fn can_partition_k_subsets(nums: Vec<i32>, k: i32) -> bool {
let n = nums.len();
let sum: i32 = nums.iter().sum();
if sum % k != 0 {
return false;
}
let mut visited: Vec<bool> = vec![false; n];
Self::search(0, 0, k as usize, &mut visited, &nums, n, sum / k)
}
fn search(
start: usize,
sum: i32,
k: usize,
visited: &mut Vec<bool>,
nums: &[i32],
n: usize,
target: i32,
) -> bool {
if k == 0 {
return true;
}
for i in start..n {
if visited[i] {
continue;
}
visited[i] = true;
if sum + nums[i] < target
&& Self::search(i + 1, sum + nums[i], k, visited, nums, n, target)
{
return true;
}
if sum + nums[i] == target && Self::search(0, 0, k - 1, visited, nums, n, target) {
return true;
}
visited[i] = false;
}
false
}
}
#[test]
fn test() {
// let nums = vec![4, 3, 2, 3, 5, 2, 1];
// let k = 4;
// let res = true;
// assert_eq!(Solution::can_partition_k_subsets(nums, k), res);
let nums = vec![2, 2, 2, 2, 3, 4, 5];
let k = 4;
let res = false;
assert_eq!(Solution::can_partition_k_subsets(nums, k), res);
}