回溯算法实践：集合划分
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 698. Partition to K Equal Sum Subsets | 🟠 |
Prerequisites
Before reading this article, you should learn:
I've mentioned before that backtracking is the most useful algorithm for written exams. If you're stuck, use backtracking for a brute-force solution. Even if it doesn't pass all test cases, it can still get you some points. The techniques of backtracking aren't too difficult; it's just the process of exhaustively searching a decision tree. You only need to "make a choice" before recursion and "undo the choice" after recursion.
However, even with brute-force enumeration, different approaches have their pros and cons. In this article, we'll look at a very classic backtracking problem, LeetCode problem #698 "Partition to K Equal Sum Subsets". This problem will help you understand the backtracking mindset more deeply and write backtracking functions with ease.
The problem is quite simple:
Given an array nums and a positive integer k, determine if nums can be partitioned into k subsets with equal sum.
The function signature is as follows:
boolean canPartitionKSubsets(int[] nums, int k);bool canPartitionKSubsets(vector<int>& nums, int k);def canPartitionKSubsets(nums: List[int], k: int) -> bool:func canPartitionKSubsets(nums []int, k int) bool {var canPartitionKSubsets = function(nums, k) {
};Thought Exercise
We previously discussed the Subset Sum Partition problem, where we needed to divide a set into two equal subsets. This problem can be transformed into a knapsack problem and solved using dynamic programming techniques.
Why can dividing a set into two equal subsets be transformed into a knapsack problem and solved with dynamic programming, but dividing it into k equal subsets cannot be transformed into a knapsack problem and can only be solved using backtracking with brute-force enumeration? Please try to think about this on your own first.
Answer to Thought Exercise
Why can dividing into two equal subsets be transformed into a knapsack problem?
In the scenario of the Subset Sum Partition problem, there is a knapsack and several items, each with two choices: either "put in the knapsack" or "not put in the knapsack." When dividing the original set S into two equal subsets S_1 and S_2, each element in S also has two choices: either "put in S_1" or "not put in S_1 (put in S_2)." The exhaustive approach here is essentially the same as in the knapsack problem.
However, if you want to divide S into k equal subsets, it means each element in S has k choices, which is fundamentally different from the standard knapsack problem scenario. Therefore, the knapsack problem-solving approach cannot be applied here.
Problem Approach
Getting back to the topic, this algorithm problem asks us to partition subsets. Subset problems differ from permutation and combination problems, but we can借鉴 the abstraction of the "ball-box model" to solve this subset partitioning problem from two different perspectives.
We need to divide an array nums containing n numbers into k subsets with equal sums. Imagine distributing n numbers into k "buckets" such that the sum of numbers in each of these k buckets is the same.
In a previous article Understanding Backtracking with the Ball-Box Model, we discussed the key to backtracking algorithms.
The key is knowing how to "make choices" so that we can use recursive functions to exhaust all possibilities.
Following the derivation logic of permutation formulas, distributing n numbers into k buckets can also be viewed from two perspectives:
Perspective One: If we switch to the perspective of these n numbers, each number must choose one of the k buckets to enter.
Perspective Two: If we switch to the perspective of these k buckets, for each bucket, we must traverse the n numbers in nums and decide whether to include the current number in that bucket.
You might wonder, what's the difference between these two perspectives?
Similar to the permutation and subset problems discussed earlier, using different perspectives for exhaustive enumeration yields the same results, but the logic and implementation of the solution code differ, potentially leading to different time and space complexities. We need to choose the solution with lower complexity.
From the Perspective of Numbers
Using a for loop to iterate through the nums array is something everyone is familiar with:
for (int index = 0; index < nums.length; index++) {
print(nums[index]);
}Do you know how to traverse an array recursively? It's actually quite simple:
void traverse(int[] nums, int index) {
if (index == nums.length) {
return;
}
print(nums[index]);
traverse(nums, index + 1);
}By simply calling traverse(nums, 0), it achieves the exact same effect as a for loop.
Returning to this problem, from the perspective of numbers, selecting k buckets and writing it with a for loop would look like this:
// k buckets (collections), record the sum of numbers in each bucket
int[] bucket = new int[k];
// enumerate each number in nums
for (int index = 0; index < nums.length; index++) {
// enumerate each bucket
for (int i = 0; i < k; i++) {
// decide whether nums[index] should go into the i-th bucket
// ...
}
}// k buckets (sets), record the sum of numbers in each bucket
int bucket[k] = {0};
// enumerate each number in nums
for(int index = 0; index < nums.size(); index++) {
// enumerate each bucket
for(int i = 0; i < k; i++) {
// decide whether nums[index] should go into the i-th bucket
// ...
}
}# k buckets (sets), record the sum of numbers in each bucket
bucket = [0] * k
# enumerate each number in nums
for index in range(len(nums)):
# enumerate each bucket
for i in range(k):
# decide whether nums[index] should go into the i-th bucket
# ...// k buckets (collections), record the sum of numbers in each bucket
bucket := make([]int, k)
// enumerate each number in nums
for index := 0; index < len(nums); index++ {
// enumerate each bucket
for i := 0; i < k; i++ {
// decide whether nums[index] should go into the i-th bucket
// ...
}
}// k buckets (collections), record the sum of numbers in each bucket
var bucket = new Array(k);
// enumerate each number in nums
for (var index = 0; index < nums.length; index++) {
// enumerate each bucket
for (var i = 0; i < k; i++) {
// decide whether nums[index] should go into the i-th bucket
// ...
}
}If we change it to a recursive form, the logic of the code would be as follows:
// k buckets (collections), record the sum of numbers in each bucket
int[] bucket = new int[k];
// enumerate each number in nums
void backtrack(int[] nums, int index) {
// base case
if (index == nums.length) {
return;
}
// enumerate each bucket
for (int i = 0; i < bucket.length; i++) {
// choose to put it into the i-th bucket
bucket[i] += nums[index];
// recursively enumerate the next number's choice
backtrack(nums, index + 1);
// undo the choice
bucket[i] -= nums[index];
}
}// k buckets (collections), record the sum of numbers in each bucket
int bucket[k];
// enumerate each number in nums
void backtrack(int nums[], int index) {
// base case
if (index == sizeof(nums)/sizeof(nums[0])) {
return;
}
// enumerate each bucket
for (int i = 0; i < sizeof(bucket)/sizeof(bucket[0]); i++) {
// choose to put it into the i-th bucket
bucket[i] += nums[index];
// recursively enumerate the next number's choice
backtrack(nums, index + 1);
// undo the choice
bucket[i] -= nums[index];
}
}# k buckets (sets), record the sum of numbers in each bucket
bucket = [0] * k
# enumerate each number in nums
def backtrack(nums: List[int], index: int):
# base case
if index == len(nums):
return
# enumerate each bucket
for i in range(len(bucket)):
# choose to put it in the i-th bucket
bucket[i] += nums[index]
# recursively enumerate the choice of the next number
backtrack(nums, index + 1)
# undo the choice
bucket[i] -= nums[index]// k buckets (sets), record the sum of numbers in each bucket
bucket := make([]int, k)
// enumerate each number in nums
func backtrack(nums []int, k int) {
// base case
if index == len(nums) {
return
}
// enumerate each bucket
for i := 0; i < len(bucket); i++ {
// choose to put it in the i-th bucket
bucket[i] += nums[index]
// recursively enumerate the next number's choice
backtrack(nums, index + 1)
// cancel the choice
bucket[i] -= nums[index]
}
}// k buckets (sets), record the sum of numbers in each bucket
var bucket = new Array(k);
// enumerate each number in nums
function backtrack(nums, index) {
// base case
if (index === nums.length) {
return;
}
// enumerate each bucket
for (var i = 0; i < bucket.length; i++) {
// choose to put it into the i-th bucket
bucket[i] += nums[index];
// recursively enumerate the choice of the next number
backtrack(nums, index + 1);
// undo the choice
bucket[i] -= nums[index];
}
}Although the above code is just a brute-force logic and cannot solve our problem yet, it can be improved with a little refinement:
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
// exclude some base cases
if (k > nums.length) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) return false;
// k buckets (sets), record the sum of numbers in each bucket
int[] bucket = new int[k];
// the theoretical sum of numbers in each bucket
int target = sum / k;
// try all possibilities, to see if nums can be divided into k subsets with sum of target
return backtrack(nums, 0, bucket, target);
}
// recursively try each number in nums
boolean backtrack(
int[] nums, int index, int[] bucket, int target) {
if (index == nums.length) {
// check if the sum of numbers in all buckets is target
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] != target) {
return false;
}
}
// successfully divide nums into k subsets
return true;
}
// try all possible buckets for nums[index]
for (int i = 0; i < bucket.length; i++) {
// pruning, the bucket is full
if (bucket[i] + nums[index] > target) {
continue;
}
// put nums[index] into bucket[i]
bucket[i] += nums[index];
// recursively try the next number's choices
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
// undo the choice
bucket[i] -= nums[index];
}
// nums[index] cannot be put into any bucket
return false;
}
}class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
// exclude some base cases
if (k > nums.size()) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) return false;
// k buckets (sets), record the sum of numbers in each bucket
vector<int> bucket(k, 0);
// the theoretical sum of numbers in each bucket
int target = sum / k;
// exhaustedly check if nums can be divided into k subsets with a sum of target
return backtrack(nums, 0, bucket, target);
}
// recursively enumerate each number in nums
bool backtrack(vector<int>& nums, int index, vector<int>& bucket, int target) {
if (index == nums.size()) {
// check if the sum of numbers in all buckets is target
for (int i = 0; i < bucket.size(); i++) {
if (bucket[i] != target) {
return false;
}
}
// nums is successfully divided into k subsets
return true;
}
// enumerate the buckets that nums[index] may be put into
for (int i = 0; i < bucket.size(); i++) {
// pruning, the bucket is full
if (bucket[i] + nums[index] > target) {
continue;
}
// put nums[index] into bucket[i]
bucket[i] += nums[index];
// recursively enumerate the choices for the next number
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
// cancel the choice
bucket[i] -= nums[index];
}
// nums[index] cannot be put into any bucket
return false;
}
};class Solution:
def canPartitionKSubsets(self, nums, k):
# exclude some base cases
if k > len(nums): return False
sum = 0
for v in nums: sum += v
if sum % k != 0: return False
# k buckets (sets), record the sum of numbers in each bucket
bucket = [0] * k
# the theoretical sum of numbers in each bucket
target = sum // k
# exhaustively check if nums can be divided into k subsets with a sum of target
return self.backtrack(nums, 0, bucket, target)
# recursively exhaust each number in nums
def backtrack(self, nums, index, bucket, target):
if index == len(nums):
# check if the sum of numbers in all buckets is target
for i in range(len(bucket)):
if bucket[i] != target:
return False
# nums is successfully divided into k subsets
return True
# exhaustively try to put nums[index] into buckets
for i in range(len(bucket)):
# pruning, the bucket is full
if bucket[i] + nums[index] > target:
continue
# put nums[index] into bucket[i]
bucket[i] += nums[index]
# recursively exhaust the next number's choices
if self.backtrack(nums, index + 1, bucket, target):
return True
# undo the choice
bucket[i] -= nums[index]
# nums[index] cannot be put into any bucket
return Falsefunc canPartitionKSubsets(nums []int, k int) bool {
// exclude some base cases
if k > len(nums) {
return false
}
sum := 0
for _, v := range nums {
sum += v
}
if sum%k != 0 {
return false
}
// k buckets (sets), record the sum of numbers in each bucket
bucket := make([]int, k)
// the theoretical sum of numbers in each bucket
target := sum / k
// try all possibilities, see if nums can be divided into k subsets with sum target
return backtrack(nums, 0, bucket, target)
}
// recursively try every number in nums
func backtrack(nums []int, index int, bucket []int, target int) bool {
if index == len(nums) {
// check if the sum of numbers in all buckets is target
for i := 0; i < len(bucket); i++ {
if bucket[i] != target {
return false
}
}
// nums is successfully divided into k subsets
return true
}
// try all possible buckets that nums[index] can go into
for i := 0; i < len(bucket); i++ {
// pruning, the bucket is full
if bucket[i]+nums[index] > target {
continue
}
// put nums[index] into bucket[i]
bucket[i] += nums[index]
// recursively try the next number's choices
if backtrack(nums, index+1, bucket, target) {
return true
}
// undo the choice
bucket[i] -= nums[index]
}
// nums[index] cannot go into any bucket
return false
}var canPartitionKSubsets = function(nums, k) {
// exclude some base cases
if (k > nums.length) return false;
var sum = 0;
for (var v of nums) sum += v;
if (sum % k != 0) return false;
// k buckets (sets), record the sum of numbers in each bucket
var bucket = new Array(k).fill(0);
// the theoretical sum of numbers in each bucket
var target = sum / k;
// try all possibilities, to see if nums can be divided into k subsets with sum of target
return backtrack(nums, 0, bucket, target);
}
// recursively try every number in nums
var backtrack = function(nums, index, bucket, target) {
if (index === nums.length) {
// check if the sum of numbers in all buckets is target
for (var i = 0; i < bucket.length; i++) {
if (bucket[i] !== target) {
return false;
}
}
// successfully divide nums into k subsets
return true;
}
// try all possible buckets for nums[index]
for (var i = 0; i < bucket.length; i++) {
// pruning, the bucket is full
if (bucket[i] + nums[index] > target) {
continue;
}
// put nums[index] into bucket[i]
bucket[i] += nums[index];
// recursively try the next number's choices
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
// revert the choice
bucket[i] -= nums[index];
}
// nums[index] cannot be put into any bucket
return false;
}With the previous foundation, this code should be relatively easy to understand. In fact, we can make one more optimization.
Focus on the recursive part of the backtrack function:
for (int i = 0; i < bucket.length; i++) {
// pruning
if (bucket[i] + nums[index] > target) {
continue;
}
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
}for (int i = 0; i < bucket.size(); i++) {
// pruning
if (bucket[i] + nums[index] > target) {
continue;
}
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
}for i in range(len(bucket)):
# pruning
if bucket[i] + nums[index] > target:
continue
if backtrack(nums, index + 1, bucket, target):
return Truefor i := 0; i < len(bucket); i++ {
// pruning
if bucket[i] + nums[index] > target {
continue
}
if backtrack(nums, index + 1, bucket, target) {
return true
}
}for (var i = 0; i < bucket.length; i++) {
// pruning
if (bucket[i] + nums[index] > target) {
continue;
}
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
}If we make as many cases as possible hit the pruning if branch, we can reduce the number of recursive calls, which to some extent reduces the time complexity.
How can we hit this if branch as often as possible? Keep in mind that our index parameter starts from 0 and increases, meaning we recursively traverse the nums array starting from 0.
If we sort the nums array in advance, placing larger numbers at the beginning, then larger numbers will be assigned to bucket first. For subsequent numbers, bucket[i] + nums[index] will be larger, making it easier to trigger the pruning if condition.
Therefore, we can add some more code to the previous code:
boolean canPartitionKSubsets(int[] nums, int k) {
// other code remains unchanged
// ...
// sort the nums array in descending order
Arrays.sort(nums);
// reverse the array to get the descending order array
for (i = 0, j = nums.length - 1; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// *****************
return backtrack(nums, 0, bucket, target);
}bool canPartitionKSubsets(vector<int>& nums, int k) {
// other code remains unchanged
// ...
// sort the nums array in descending order
sort(nums.begin(), nums.end(), greater<int>());
// *****************
return backtrack(nums, 0, bucket, target);
}def canPartitionKSubsets(nums: List[int], k: int) -> bool:
# other code remains unchanged
# ...
# sort the nums array in descending order
nums.sort(reverse=True)
# ****************
return backtrack(nums, 0, bucket, target)func canPartitionKSubsets(nums []int, k int) bool {
// other code remains unchanged
// ...
// sort the nums array in descending order
sort.Slice(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
// *****************
return backtrack(nums, 0, bucket, target)
}var canPartitionKSubsets = function(nums, k) {
// other code remains unchanged
// ...
// sort the nums array in descending order
nums.sort((a, b) => b - a);
// *****************
return backtrack(nums, 0, bucket, target);
}This solution can get the correct answer, but it takes a lot of time and can no longer pass all test cases. Let's look at another perspective.
Bucket Perspective
As mentioned at the beginning of the article, from the bucket's perspective, we need to iterate through all numbers in nums for each bucket to decide whether to put the current number into the bucket; once a bucket is filled, we move on to the next one until all buckets are filled.
This approach can be represented by the following code:
// fill all the buckets until
while (k > 0) {
// record the sum of numbers in the current bucket
int bucket = 0;
for (int i = 0; i < nums.length; i++) {
// decide whether to put nums[i] into the current bucket
if (canAdd(bucket, num[i])) {
bucket += nums[i];
}
if (bucket == target) {
// filled one bucket, move on to the next one
k--;
break;
}
}
}// fill all the buckets until
while (k > 0) {
// record the sum of numbers in the current bucket
int bucket = 0;
for (int i = 0; i < nums.size(); i++) {
// decide whether to put nums[i] into the current bucket
if (canAdd(bucket, nums[i])) {
bucket += nums[i];
}
if (bucket == target) {
// filled one bucket, move on to the next bucket
k--;
break;
}
}
}# Fill all the buckets until
while k > 0:
# Record the sum of numbers in the current bucket
bucket = 0
for i in range(len(nums)):
# Decide whether to put nums[i] into the current bucket
if canAdd(bucket, nums[i]):
bucket += nums[i]
if bucket == target:
# Filled one bucket, move on to the next bucket
k -= 1
break// fill all the buckets until
for k > 0 {
// record the sum of numbers in the current bucket
bucket := 0
for i := 0; i < len(nums); i++ {
// decide whether to put nums[i] into the current bucket
if canAdd(bucket, nums[i]) {
bucket += nums[i]
}
if bucket == target {
// filled one bucket, move on to the next one
k--
break
}
}
}// declare a function using var
var fillBuckets = function(nums, k, target) {
// fill all the buckets until
while (k > 0) {
// record the sum of numbers in the current bucket
var bucket = 0;
for (var i = 0; i < nums.length; i++) {
// decide whether to put nums[i] into the current bucket
if (canAdd(bucket, nums[i])) {
bucket += nums[i];
}
if (bucket == target) {
// filled one bucket, move on to the next one
k--;
break;
}
}
}
}Similarly, we can also rewrite this while loop as a recursive function, which is a bit more complex. First, let's define a backtrack recursive function:
boolean backtrack(int k, int bucket, int[] nums, int start, boolean[] used, int target);bool backtrack(int k, int bucket, int nums[], int start, bool used[], int target);def backtrack(k: int, bucket: int, nums: List[int], start: int, used: List[bool], target: int) -> bool:func backtrack(k int, bucket int, nums []int, start int, used []bool, target int) boolvar backtrack = function(k, bucket, nums, start, used, target): bool {}Don't be intimidated by so many parameters; I'll explain each one step by step. If you have a thorough understanding of the previous article Understanding Backtracking with the Ball and Box Model, you'll be able to write such a backtracking function effortlessly.
The parameters of this backtrack function can be explained as follows:
Currently, bucket k is considering whether to include the element nums[start]; the sum of the numbers already in bucket k is bucket; the used flag indicates whether a particular element has been placed in a bucket; target is the goal sum that each bucket needs to achieve.
Based on this function definition, you can call the backtrack function like this:
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
// exclude some base cases
if (k > nums.length) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) return false;
boolean[] used = new boolean[nums.length];
int target = sum / k;
// the k-th bucket is initially empty, start making choices from nums[0]
return backtrack(k, 0, nums, 0, used, target);
}
}class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
// Exclude some base cases
if (k > nums.size()) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) return false;
vector<bool> used(nums.size(), false);
int target = sum / k;
// k-th bucket initially has nothing, start making choices from nums[0]
return backtrack(k, 0, nums, 0, used, target);
}
};class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
# Exclude some base cases
if k > len(nums): return False
sum_ = sum(nums)
if sum_ % k != 0: return False
used = [False] * len(nums)
target = sum_ // k
# The k-th bucket is initially empty, start making choices from nums[0]
return self.backtrack(k, 0, nums, 0, used, target)func canPartitionKSubsets(nums []int, k int) bool {
// exclude some base cases
if k > len(nums) {
return false
}
sum := 0
for _, v := range nums {
sum += v
}
if sum % k != 0 {
return false
}
used := make([]bool, len(nums))
target := sum / k
// the k-th bucket is initially empty, start making choices from nums[0]
return backtrack(k, 0, nums, 0, used, target)
}var canPartitionKSubsets = function(nums, k) {
// exclude some base cases
if (k > nums.length) return false;
var sum = 0;
for (var i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % k !== 0) return false;
var used = new Array(nums.length).fill(false);
var target = sum / k;
// start with kth bucket empty, make choices starting from nums[0]
return backtrack(k, 0, nums, 0, used, target);
};Before implementing the logic of the backtrack function, let's reiterate the perspective from the bucket's viewpoint:
We need to traverse all numbers in
numsto decide which numbers should be placed in the current bucket.If the current bucket is full (the sum of numbers in the bucket reaches
target), then start the first step for the next bucket.
The following code implements this logic:
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
// see the above text
}
boolean backtrack(int k, int bucket,
int[] nums, int start, boolean[] used, int target) {
// base case
if (k == 0) {
// all buckets are full, and nums must all be used up
// because target == sum / k
return true;
}
if (bucket == target) {
// the current bucket is full, recursively enumerate the choices for the next bucket
// let the next bucket start selecting numbers from nums[0]
return backtrack(k - 1, 0 ,nums, 0, used, target);
}
// start from start to look back for valid nums[i] to put into the current bucket
for (int i = start; i < nums.length; i++) {
// pruning
if (used[i]) {
// nums[i] has already been placed in another bucket
continue;
}
if (nums[i] + bucket > target) {
// the current bucket cannot hold nums[i]
continue;
}
// make a choice, put nums[i] into the current bucket
used[i] = true;
bucket += nums[i];
// recursively enumerate whether the next number should be placed in the current bucket
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
// cancel the choice
used[i] = false;
bucket -= nums[i];
}
// having exhausted all numbers, none can fill the current bucket
return false;
}
}class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
// see the above text
}
bool backtrack(int k, int bucket,
vector<int>& nums, int start, vector<bool>& used, int target) {
// base case
if (k == 0) {
// all buckets are full, and nums are definitely all used up
// because target == sum / k
return true;
}
if (bucket == target) {
// the current bucket is full, recursively enumerate the choices for the next bucket
// let the next bucket start picking numbers from nums[0]
return backtrack(k - 1, 0 ,nums, 0, used, target);
}
// start from start to look back for valid nums[i] to put into the current bucket
for (int i = start; i < nums.size(); i++) {
// pruning
if (used[i]) {
// nums[i] has already been put into another bucket
continue;
}
if (nums[i] + bucket > target) {
// the current bucket cannot hold nums[i]
continue;
}
// make a choice, put nums[i] into the current bucket
used[i] = true;
bucket += nums[i];
// recursively enumerate whether the next number should be put into the current bucket
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
// cancel the choice
used[i] = false;
bucket -= nums[i];
}
// all numbers have been exhausted, and the current bucket cannot be filled
return false;
}
};class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
# see above
def backtrack(self, k: int, bucket: int, nums: List[int],
start: int, used: List[bool], target: int) -> bool:
# base case
if k == 0:
# all buckets are full, and nums must be all used up
# because target == sum / k
return True
if bucket == target:
# filled the current bucket, recursively enumerate the choices for the next bucket
# let the next bucket start picking numbers from nums[0]
return self.backtrack(k - 1, 0, nums, 0, used, target)
# start from start to look back for valid nums[i] to put into the current bucket
for i in range(start, len(nums)):
# pruning
if used[i]:
# nums[i] has already been put into another bucket
continue
if nums[i] + bucket > target:
# the current bucket cannot hold nums[i]
continue
# make a choice, put nums[i] into the current bucket
used[i] = True
bucket += nums[i]
# recursively enumerate whether to put the next number into the current bucket
if self.backtrack(k, bucket, nums, i + 1, used, target):
return True
# cancel the choice
used[i] = False
bucket -= nums[i]
# have tried all numbers, none can fill the current bucket
return Falsefunc canPartitionKSubsets(nums []int, k int) bool {
// see the above text
}
func backtrack(k int, bucket int, nums []int, start int, used []bool, target int) bool {
// base case
if k == 0 {
// all buckets are full, and nums are definitely all used up
// because target == sum / k
return true
}
if bucket == target {
// filled the current bucket, recursively enumerate the choices for the next bucket
// let the next bucket start picking numbers from nums[0]
return backtrack(k-1, 0, nums, 0, used, target)
}
// start from start to look back for valid nums[i] to put into the current bucket
for i := start; i < len(nums); i++ {
// pruning
if used[i] {
// nums[i] has already been put into another bucket
continue
}
if nums[i] + bucket > target {
// the current bucket cannot hold nums[i]
continue
}
// make a choice, put nums[i] into the current bucket
used[i] = true
bucket += nums[i]
// recursively enumerate whether the next number should be put into the current bucket
if backtrack(k, bucket, nums, i+1, used, target) {
return true
}
// cancel the choice
used[i] = false
bucket -= nums[i]
}
// have tried all numbers, none can fill the current bucket
return false
}var canPartitionKSubsets = function(nums, k) {
// see the above text
}
var backtrack = function(k, bucket, nums, start, used, target) {
// base case
if (k == 0) {
// all buckets are filled, and nums are definitely all used up
// because target == sum / k
return true;
}
if (bucket == target) {
// the current bucket is filled, recursively enumerate the next bucket's choices
// let the next bucket start selecting numbers from nums[0]
return backtrack(k - 1, 0, nums, 0, used, target);
}
// start from 'start' to look back for valid nums[i] to put into the current bucket
for (var i = start; i < nums.length; i++) {
// pruning
if (used[i]) {
// nums[i] has already been placed in another bucket
continue;
}
if (nums[i] + bucket > target) {
// the current bucket cannot hold nums[i]
continue;
}
// make a choice, put nums[i] into the current bucket
used[i] = true;
bucket += nums[i];
// recursively enumerate whether to put the next number into the current bucket
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
// revert the choice
used[i] = false;
bucket -= nums[i];
}
// having tried all numbers, none can fill the current bucket
return false;
};This code can produce the correct answer, but it is inefficient. Let's think about whether there is room for optimization.
Firstly, in this solution, each bucket can be considered identical, but our backtracking algorithm treats them differently, leading to redundant calculations.
What does this mean? Our backtracking algorithm essentially exhaustively explores all possible combinations to see if it can find k buckets (subsets) that sum up to target.
For example, in the following scenario with target = 5, the algorithm might place 1, 4 in the first bucket:
Now that the first bucket is full, it starts filling the second bucket with 2, 3:
This process continues, exhaustively exploring elements to form subsets that sum up to 5.
But what happens if it ultimately finds that it cannot form k subsets that sum up to target?
The backtracking algorithm will backtrack to the first bucket and start over. Knowing that 1, 4 in the first bucket is not feasible, it will try placing 2, 3 in the first bucket:
Now that the first bucket is full, it starts filling the second bucket with 1, 4:
At this point, you should notice the problem: this situation is actually the same as the previous one. In other words, you already know that further exhaustive exploration is unnecessary, as it is impossible to form k subsets that sum up to target.
However, our algorithm will continue to explore naively because it sees the first and second buckets as containing different elements, thus considering them different scenarios.
So, how can we make the algorithm smarter to recognize this situation and avoid redundant calculations?
Notice that the used array in both scenarios will look the same, so the used array can be considered the "state" during the backtracking process.
Therefore, we can use a memo to record the current state of used when a bucket is filled. If the current state of used has appeared before, there is no need to continue exploring, thus pruning and avoiding redundant calculations.
Some readers might ask, how can the used boolean array be used as a key for storage? This is a minor issue. For example, we can convert the array into a string, which can then be used as a key in a hash table.
Let's look at the code implementation. Only a slight modification to the backtrack function is needed:
class Solution {
// Memoization, storing the state of the used array
HashMap<String, Boolean> memo = new HashMap<>();
public boolean canPartitionKSubsets(int[] nums, int k) {
// See above
}
boolean backtrack(int k, int bucket, int[] nums, int start, boolean[] used, int target) {
// base case
if (k == 0) {
return true;
}
// Convert the state of used into a string like [true, false, ...]
// for easy storage in the HashMap
String state = Arrays.toString(used);
if (bucket == target) {
// The current bucket is filled, recursively enumerate the choices for the next bucket
boolean res = backtrack(k - 1, 0, nums, 0, used, target);
// Store the current state and result in the memoization
memo.put(state, res);
return res;
}
if (memo.containsKey(state)) {
// If the current state has been calculated before, return directly without further recursion
return memo.get(state);
}
// Other logic remains unchanged...
return false; // This was added to complete the code, it's not a comment.
}
}class Solution {
// memo, stores the state of the used array
std::unordered_map<std::string, bool> memo;
public:
bool canPartitionKSubsets(std::vector<int>& nums, int k) {
// see above
}
bool backtrack(int k, int bucket, std::vector<int>& nums, int start, std::vector<bool>& used, int target) {
// base case
if (k == 0) {
return true;
}
// convert the state of used into a string like [true, false, ...]
// convenient for storing in unordered_map
std::string state = "";
for(auto val: used) // convert vector to string
state += (val) ? "true," : "false,";
if (bucket == target) {
// when the current bucket is full, recursively enumerate the choices for the next bucket
bool res = backtrack(k - 1, 0, nums, 0, used, target);
// store the current state and result into the memo
memo[state] = res;
return res;
}
if (memo.count(state)) {
// if the current state has been calculated before, return directly without further recursion
return memo[state];
}
// other logic remains unchanged...
}
}class Solution:
def __init__(self):
# memo, stores the state of the used array
self.memo = {}
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
# see above
def backtrack(self, k: int, bucket: int, nums: List[int],
start: int, used: List[bool], target: int) -> bool:
# base case
if k == 0:
return True
# convert the state of used into a string like [true, false, ...]
# for easy storage in HashMap
state = str(used)
if bucket == target:
# the current bucket is full, recursively enumerate the choices for the next bucket
res = self.backtrack(k - 1, 0, nums, 0, used, target)
# store the current state and result in the memo
self.memo[state] = res
return res
if state in self.memo:
# if the current state has been computed before, return directly, no need to recursively enumerate
return self.memo[state]
# other logic remains unchanged...// memo, store the state of the used array
var memo = make(map[string]bool)
func canPartitionKSubsets(nums []int, k int) bool {
// see above
}
func backtrack(k int, bucket int, nums []int, start int, used []bool, target int) bool {
// base case
if k == 0 {
return true
}
// convert the state of used into a string like [true, false, ...]
// convenient for storing into HashMap
state := strings.Join(strings.Fields(fmt.Sprint(used)), ",")
if bucket == target {
// current bucket is full, recursively enumerate the selection of the next bucket
res := backtrack(k - 1, 0, nums, 0, used, target)
// store the current state and result into the memo
memo[state] = res
return res
}
if _, ok := memo[state]; ok {
// if the current state has been calculated before, return directly, don't recursively enumerate
return memo[state]
}
// other logic remains unchanged...
}// Memoization, store the state of the used array
var memo = {};
var canPartitionKSubsets = function(nums, k) {
// See above
}
var backtrack(k, bucket, nums, start, used, target) = function {
// base case
if (k == 0) {
return true;
}
// Convert the state of used to a string like [true, false, ...]
// For easy storage in HashMap
var state = JSON.stringify(used);
if (bucket == target) {
// Current bucket is full, recursively enumerate the choice for the next bucket
var res = backtrack(k - 1, 0, nums, 0, used, target);
// Store the current state and result in the memo
memo[state] = res;
return res;
}
if (state in memo) {
// If the current state has been computed before, return immediately without further recursion
return memo[state];
}
// Other logic remains unchanged...
}Submitting the solution this way, you may find that the execution efficiency is still relatively low. This time, it's not due to redundant calculations in the algorithm logic, but rather an issue with the code implementation.
The problem is that converting the used array to a string in each recursive call is a significant overhead for the programming language, so we can further optimize this.
Note that the problem specifies the data size as nums.length <= 16, meaning the used array will never exceed 16 elements. Therefore, we can use the technique of a "bitmap" to replace the used array with an int-type used variable.
Specifically, we can use the i-th bit of the integer used (i.e., (used >> i) & 1) to represent the true/false value of used[i].
This approach not only saves space but also allows the integer used to be directly used as a key in the HashMap, eliminating the overhead of converting the array to a string.
Here is the final solution code:
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
// exclude some basic cases
if (k > nums.length) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) return false;
// use bit manipulation technique
int used = 0;
int target = sum / k;
// the k-th bucket initially has nothing, start choosing from nums[0]
return backtrack(k, 0, nums, 0, used, target);
}
HashMap<Integer, Boolean> memo = new HashMap<>();
boolean backtrack(int k, int bucket,
int[] nums, int start, int used, int target) {
// base case
if (k == 0) {
// all buckets are filled, and all nums must have been used
return true;
}
if (bucket == target) {
// current bucket is filled, recursively enumerate the choices for the next bucket
// let the next bucket start choosing from nums[0]
boolean res = backtrack(k - 1, 0, nums, 0, used, target);
// cache the result
memo.put(used, res);
return res;
}
if (memo.containsKey(used)) {
// avoid redundant calculations
return memo.get(used);
}
for (int i = start; i < nums.length; i++) {
// pruning
// check if the i-th bit is 1
if (((used >> i) & 1) == 1) {
// nums[i] has already been used in another bucket
continue;
}
if (nums[i] + bucket > target) {
continue;
}
// make a choice
// set the i-th bit to 1
used |= 1 << i;
bucket += nums[i];
// recursively enumerate whether the next number goes into the current bucket
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
// undo the choice
// use XOR operation to reset the i-th bit to 0
used ^= 1 << i;
bucket -= nums[i];
}
return false;
}
}class Solution {
public:
//备忘录
unordered_map<int, bool> memo;
bool backtrack(int k, int bucket, vector<int>& nums, int start, int used, int target) {
if (k == 0) {
// All buckets are filled, and all nums must be used up
return true;
}
if (bucket == target) {
// The current bucket is full, recursively enumerate the choices for the next bucket
// Let the next bucket start choosing numbers from nums[0]
bool res = backtrack(k - 1, 0, nums, 0, used, target);
// Cache the result
memo[used] = res;
return res;
}
if (memo.count(used)) {
// Avoid redundant calculations
return memo[used];
}
for (int i = start; i < nums.size(); i++) {
// Pruning
// Check if the i-th bit is 1
if ((used >> i) & 1 == 1) {
// nums[i] has already been placed in another bucket
continue;
}
if (nums[i] + bucket > target) {
// Can't fit, pruning
continue;
}
// Make a choice
// Set the i-th bit to 1
used |= 1 << i;
bucket += nums[i];
// Recursively enumerate whether the next number should be placed in the current bucket
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
// Undo the choice
// Use XOR operation to reset the i-th bit to 0
used ^= 1 << i;
bucket -= nums[i];
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
// Exclude some basic cases
if (k > nums.size()) return false;
int sum = 0;
for (int v : nums) sum += v;
if (sum % k != 0) {
// Cannot be divided evenly, exit early
return false;
}
// Use bitmap technique to record whether each element has been selected
int used = 0;
int target = sum / k;
// The k-th bucket starts empty, begin choosing from nums[0]
return backtrack(k, 0, nums, 0, used, target);
}
};class Solution:
def __init__(self):
# memoization, storing the state of the used array
self.memo = {}
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
# exclude some base cases
if k > len(nums):
return False
sum = 0
for v in nums:
sum += v
if sum % k != 0:
# not divisible, exit early
return False
# use bit manipulation technique
used = 0
target = sum // k
# k-th bucket starts empty, make choices starting from nums[0]
return self.backtrack(k, 0, nums, 0, used, target)
def backtrack(self, k: int, bucket: int, nums: List[int],
start: int, used: int, target: int) -> bool:
if k == 0:
return True
state = str(used)
if bucket == target:
# filled the current bucket, recursively enumerate the choices for the next bucket
res = self.backtrack(k - 1, 0, nums, 0, used, target)
# cache the result
self.memo[state] = res
return res
if state in self.memo:
# avoid redundant calculations
return self.memo[state]
for i in range(start, len(nums)):
if (used >> i) & 1 == 1:
# nums[i] has already been put into another bucket
continue
if nums[i] + bucket > target:
# cannot fit, prune the search space
continue
# make a choice
used |= 1 << i
bucket += nums[i]
# recursively enumerate whether to put the next number into the current bucket
if self.backtrack(k, bucket, nums, i + 1, used, target):
return True
# revert the choice
used ^= 1 << i
bucket -= nums[i]
return Falsefunc canPartitionKSubsets(nums []int, k int) bool {
// exclude some basic cases
if k > len(nums) {
return false
}
sum := 0
for _, v := range nums {
sum += v
}
if sum % k != 0 {
// not divisible, exit early
return false
}
// use bit manipulation trick
used := 0
target := sum / k
// memoization
memo := make(map[int]bool)
// k-th bucket initially empty, start making choices from nums[0]
return backtrack(k, 0, nums, 0, used, target, memo)
}
func backtrack(k, bucket int, nums []int, start int, used int, target int, memo map[int]bool) bool {
// base case
if k == 0 {
// all buckets are full and nums are definitely all used up
return true
}
if bucket == target {
// current bucket is full, recursively enumerate the choices for the next bucket
// let the next bucket start picking numbers from nums[0]
res, ok := memo[used]
if !ok {
res = backtrack(k-1, 0, nums, 0, used, target, memo)
// cache the result
memo[used] = res
}
return res
}
if res, ok := memo[used]; ok {
// avoid redundant calculations
return res
}
for i := start; i < len(nums); i++ {
// pruning
if (used >> i) & 1 == 1 {
// nums[i] has already been put into another bucket
continue
}
if nums[i] + bucket > target {
// can't fit, prune
continue
}
// make a choice
used |= 1 << i
bucket += nums[i]
// recursively enumerate whether the next number should be put into the current bucket
if backtrack(k, bucket, nums, i+1, used, target, memo) {
return true
}
// undo the choice
used ^= 1 << i
bucket -= nums[i]
}
return false
}var canPartitionKSubsets = function(nums, k) {
// exclude some basic cases
if (k > nums.length) return false;
var sum = nums.reduce((a, b) => a + b, 0);
if (sum % k !== 0) return false;
// use bitmap technique
var used = 0;
var target = sum / k;
return backtrack(k, 0, nums, 0, used, target, new Map());
};
function backtrack(k, bucket, nums, start, used, target, memo) {
// base case
if (k === 0) {
// all buckets are filled, and nums must all be used up
return true;
}
if (bucket === target) {
// current bucket is filled; recursively enumerate choices for the next bucket
// let the next bucket start choosing numbers from nums[0]
var res = backtrack(k - 1, 0, nums, 0, used, target, memo);
// cache the result
memo.set(used, res);
return res;
}
if (memo.has(used)) {
// avoid redundant calculations
return memo.get(used);
}
for (var i = start; i < nums.length; i++) {
// pruning
// check if the ith bit is 1
if (((used >> i) & 1) === 1) {
// nums[i] has already been placed in another bucket
continue;
}
if (nums[i] + bucket > target) {
continue;
}
// make a choice
// set the ith bit to 1
used |= 1 << i;
bucket += nums[i];
// recursively enumerate whether the next number fits into the current bucket
if (backtrack(k, bucket, nums, i + 1, used, target, memo)) {
return true;
}
// undo the choice
// use XOR to reset the ith bit to 0
used ^= 1 << i;
bucket -= nums[i];
}
return false;
}With this, the second approach to this problem is also completed.
Final Summary
Both approaches discussed in this article can yield the correct answer. However, even with sorting optimization, the first method is significantly slower than the second. Why is that?
Let's analyze the time complexity of these two algorithms, assuming the number of elements in nums is n.
For the first approach, which involves exhaustive enumeration from a numerical perspective, there are n numbers, and each number has k buckets to choose from. Therefore, the number of possible combinations is k^n, and the time complexity is O(k^n).
In the second approach, each bucket needs to traverse n numbers, and for each number, there are two choices: "include" or "exclude." Thus, there are 2^n possible combinations; with k buckets, the total time complexity is O(k*2^n).
Of course, this is a rough estimate of the worst-case complexity upper bound. The actual complexity is likely much better, given all the pruning logic we've added. However, even from the upper bound, it's clear that the first approach is much slower.
So, who says backtracking algorithms lack technique? While backtracking is essentially brute-force enumeration, there are smart and inefficient ways to enumerate. The key is whose "perspective" you use for the enumeration.
In layman's terms, we should aim for "fewer but more frequent" choices. That means it's better to make more choices (multiplicative relationship) rather than provide a large choice space (exponential relationship). Making n "choose one out of k" choices just once (O(k^n)) is much less efficient than making n "choose one out of two" choices k times (O(k*2^n)).
Alright, in this problem, we enumerated from two perspectives. Although the code may seem extensive, the core logic is similar. I believe this article will help you gain a deeper understanding of backtracking algorithms.
