146. Equal Sum Subsets with K Changes
Equal Sum Subsets with K Changes
You are given a list of integers nums.
Divide the list into two non-empty disjoint subsets such that every element of nums belongs to exactly one subset.
The two subsets form valid equal sum parts if the sum of the values in the first subset is the same as the sum of the values in the second subset.
Number of elements in subsets may be different.
Order does not matter. Only the chosen grouping matters.
The follow-up allows changing at most k numbers before forming the two subsets. For this problem, one change means selecting one index and either increasing or decreasing its value by exactly 1. Each index may be changed at most once, and every value must remain positive after the change.
Method Signatures
boolean canDivideIntoEqualParts(List<Integer> nums)
- Return
true if nums can be split into two non-empty disjoint subsets with the same sum.
- Return
false otherwise.
boolean canDivideIntoEqualPartsWithKChanges(List<Integer> nums, int k)
- You may change at most
k elements before dividing the list.
- One change means selecting one index and applying exactly one of the following operations:
nums[i] = nums[i] + 1
nums[i] = nums[i] - 1, only if the new value is still positive
- Each index may be changed at most once.
- Return
true if the updated list can be split into two non-empty disjoint subsets with the same sum.
- Return
false otherwise.
Constraints
2 ≤ nums.size() ≤ 200
1 ≤ nums[i] ≤ 100
0 ≤ k ≤ nums.size()
Examples
Example 1
canDivideIntoEqualParts(nums = List.of(2, 2, 3, 3))
Returns: true
Explanation: One valid split is [2, 3] and [2, 3].
Example 2
canDivideIntoEqualParts(nums = List.of(2, 3, 7))
Returns: false
Explanation: No way of assigning all three values into two non-empty groups produces the same sum on both sides.
Example 3
canDivideIntoEqualPartsWithKChanges(nums = List.of(1, 2, 4, 6), k = 1)
Returns: true
Explanation: Change the value 4 to 5. The updated list becomes [1, 2, 5, 6]. One valid split is [1, 6] and [2, 5].
Example 4
canDivideIntoEqualPartsWithKChanges(nums = List.of(1, 3), k = 1)
Returns: false
Explanation: After at most one allowed single-step change, the possible lists are [2, 3], [1, 2], or [1, 4]. None of them can be split into two non-empty subsets with equal sum.