After reading this article, you can try to solve the following problems:
698. Divided into k equal subsets (Medium)
I said that the backtracking algorithm is the best algorithm to use in the written test, so if you don’t have any ideas, you can use backtracking algorithm to solve by brute force, even if you can’t pass all the test cases, you can pass a little bit.
The technique of backtracking algorithm is also not difficult. As mentioned in the framework of backtracking algorithm, backtracking algorithm is the process of exhaustively selecting a decision tree. As long as you “make a choice” before recursion and “undo the choice” after recursion, it is ok.
But there are pros and cons to different approaches to violence.
This article will look at a very classic backtracking algorithm problem, subset partition problem, can help you more profound understanding of backtracking algorithm thinking, easily write backtracking function.
The title is very simple:
Given an array nums and a positive integer k, determine whether nums can be bisected into elements and the same k subsets.
The function signature is as follows:
boolean canPartitionKSubsets(int[] nums, int k);
Copy the codeWe talked about the backtracking algorithm framework before, what’s the key to backtracking?
The key is to know how to “make choices” so that you can use recursive functions to do exhaustive work.
So thinking back to our problem of distributing N numbers into K buckets, we can look at it in two ways:
View one, if we switch to the view of these n numbers, each number has to choose to go into one of k buckets.
View 2, if we switch to the view of the k buckets, for each bucket, we iterate over the N numbers in NUMS, and then choose whether to put the currently traversed numbers into our own bucket.
You may ask, what is the difference between these two perspectives?
Using different perspectives to do exhaustive work, although the results are the same, but the logic of the solution code is completely different; Comparing different exhaustive perspectives can help you understand backtracking algorithms more deeply, but we’ll talk about it.
Second, from the perspective of numbers
Iterating through a NUMS array with a for loop is something you can do:
for (int index = 0; index < nums.length; index++) {
System.out.println(nums[index]);
}
Copy the codeDo you know how to recurse through groups of numbers? It’s actually quite simple:
void traverse(int[] nums, int index) {
if (index == nums.length) {
return;
}
System.out.println(nums[index]);
traverse(nums, index + 1);
}
Copy the codeJust call traverse(nums, 0) and the for loop will have exactly the same effect.
So back to the problem, in terms of numbers, pick k buckets, and write it out with a for loop like this:
Int [] bucket = new int[k]; // bucket = new int[k]; For (int index = 0; index < nums.length; Index++) {// for (int I = 0; i < k; I ++) {// nums[index] selects whether to enter the I bucket //... }}Copy the codeIn recursive form, this is the code logic:
Int [] bucket = new int[k]; // bucket = new int[k]; Void backtrack(int[] nums, int index) {// Base case if (index == nums.length) {return; } for (int I = 0; i < bucket.length; Bucket [I] += nums[index]; Backtrack (nums, index + 1); backtrack(nums, index + 1); Bucket [I] -= nums[index]; }}Copy the codeWhile the above code is just exhaustive logic and does not solve our problem, it can be improved a bit:
Public Boolean canPartitionKSubsets(int[] nums, int k) {if (k > nums.length) return false; int sum = 0; for (int v : nums) sum += v; if (sum % k ! = 0) return false; Int [] bucket = new int[k]; // bucket = new int[k]; Int target = sum/k; Backtrack (nums, 0, bucket, target); backtrack(nums, 0, target); } backtrack(int[] nums, int index, int[] bucket, Int target) {if (index == nums.length) {// Check whether the sum of all buckets is target for (int I = 0; i < bucket.length; i++) { if (bucket[i] ! = target) { return false; }} // nums is split into k subsets. Return true; } for (int I = 0; i < bucket.length; If (bucket[I] + nums[index] > target) {continue; } // insert nums[index] into bucket[I] bucket[I] += nums[index]; If (backtrack(nums, index + 1, bucket, target)) {return true; } // undo bucket[I] -= nums[index]; } // nums[index] return false; }Copy the codeWith previous foreshadowing, I believe that this code is relatively easy to understand. Although this solution can be passed, it takes a lot of time. In fact, we can make another optimization.
Backtrack: backtrack:
for (int i = 0; i < bucket.length; If (bucket[I] + nums[index] > target) {continue; } if (backtrack(nums, index + 1, bucket, target)) { return true; }}Copy the codeIf we let as many cases as possible hit the pruned if branch, we can reduce the number of recursive calls and reduce time complexity to some extent.
How do you hit as many if branches as possible? Remember that our index argument increments from 0, that is, iterating recursively from 0 through the NUMS array.
If we sort the NUMS array in advance and rank the large numbers first, then the large numbers will be allocated to the bucket first. For the subsequent numbers, bucket[I] + NUMs [index] will be larger, making it easier to trigger the prune if condition.
So you can add some more code to the previous code:
Public Boolean subsets (int[] nums, int k) {public Boolean subsets (int[] nums, int k) { /* Arrays. Sort (nums); int i = 0, j = nums.length - 1; for (; i < j; I++, j -) {/ / exchange nums [I] and nums [j]. Int temp = nums [I]; nums[i] = nums[j]; nums[j] = temp; } /*******************/ return backtrack(nums, 0, bucket, target); }Copy the codeDue to the nature of the Java language, this code is sorted in descending order by ascending order and then reversing order.
Three, from the perspective of the barrel
Each bucket needs to iterate over all the numbers in numS and decide whether to put the current number into the bucket. When one bucket is filled, another bucket must be filled until all are filled.
This idea can be expressed in the following code:
While (k > 0) {int bucket = 0; for (int i = 0; i < nums.length; I ++) {bucket += nums[I] or 0; If (bucket == target) {// if (bucket == target) { break; }}}Copy the codeWe can also rewrite the while loop as a recursive function, but it is slightly more complicated. We can write a backtrack recursive function:
boolean backtrack(int k, int bucket,
int[] nums, int start, boolean[] used, int target);
Copy the codeDon’t be intimidated by the number of parameters, I’ll explain them one by one. If you understand this article thoroughly, you should be comfortable writing backtracking functions like this.
The arguments to the backtrack function can be interpreted as follows:
Now bucket K is wondering if it should include the element nums[start]; The sum of the numbers in bucket K is bucket; Used indicates whether an element is already in the bucket. Target is the sum of the goals that each bucket needs to achieve.
According to this function definition, the backtrack function can be called as follows:
Public Boolean canPartitionKSubsets(int[] nums, int k) {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; Backtrack (k, 0, nums, 0, used, target); backtrack(k, 0, nums, 0, used, target); }Copy the codeBefore implementing the logic of the backtrack function, once again, from the perspective of the bucket:
1. You need to traverse all numS numbers to determine which numbers need to be added to the current bucket.
2. If the current bucket is full (bucket number and target reached), let the next bucket start step 1.
The following code implements this logic:
boolean backtrack(int k, int bucket, int[] nums, int start, boolean[] used, Int target) {// base case if (k == 0) {// Target == sum/k return true; } if (bucket == target) { Backtrack (k-1, 0, nums, 0, used, target); backtrack(k-1, 0, nums, 0, used, target); } for (int I = start; i < nums.length; I ++) {// Prune if (used[I]) {// nums[I] has been loaded into another bucket continue; } if (nums[I] + bucket > target) {nums[I] continue; } // Add nums[I] to the bucket used[I] = true; bucket += nums[i]; Backtrack (k, bucket, nums, I + 1, used, target)) {return true; backtrack(k, bucket, nums, I + 1, used, target); } // Undo used[I] = false; bucket -= nums[i]; } return false; }Copy the codeSo that completes the second way of thinking about the problem.
Fourth, the final summary
Both approaches in this article can pass all test cases, but the first solution is significantly slower than the second solution, even after sorting optimization. Why is this?
Let’s analyze the time complexity of these two algorithms, assuming that the number of elements in NUMS is N.
So the first solution, which is to do it numerically, is n numbers, and each number has k buckets to choose from, so the number of combinations is k to the n, which is O(k to the n).
In the second solution, each bucket iterates n numbers and selects “load” or “not load”, resulting in 2^ N combinations; And we have k buckets, so the total time is order k times 2 to the n.
Of course, this is the theoretical worst, but the actual complexity is definitely better, given all the pruning logic we’ve added. However, the upper bound of complexity already shows that the first way of thinking is much slower.
So, who says backtracking algorithms aren’t tricky? Although exhaustive backtracking algorithm is violence, exhaustion is clever way of exhaustion and inefficient way of exhaustion, whose “view” key to see you with exhaustion.
In layman’s terms, we should try to “make a few more choices”, that is, we would rather make a few more choices than give too much choice. It is better to choose k times than to choose k once.
Although the amount of code seems large, the core logic is similar. I believe you can understand the backtracking algorithm more deeply through this article.
The list of essential articles is here at 🔗
View more quality algorithm articles click here, hand with your brush force buckle, committed to the algorithm to speak clearly! My algorithm tutorial has received 90K star, welcome to like!