77. Combinations
Given two integers n and k, return all possible combinations of k numbers in the range [1, n].
You can return the answers in any order.
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4].
[1,2].
[1,3].
[1,4].
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Tip:
1 <= n <= 20
1 <= k <= n
Positive solution (backtracking)
The straightforward solution is of course to use a for loop, e.g., if k is 2 in the example, it's easy to think of two for loops that will produce the same result as in the example.
Input: n = 100, k = 3 Then three levels of for loop
What if n is 100 and k is 50
At this point you'll realize that although you want to search violently, you can't even write violently with a nested for loop
Above we said that to solve the case where n is 100 and k is 50, the violent writing method requires nesting 50 layers of for loops, then the backtracking method uses recursion to solve the problem of the number of nested layers.
Recursion to do cascading nesting (can be understood as opening k layers of for loops), each recursion nested in a for loop, then recursion can be used to solve the problem of multi-layer nested loops.
- The return value of a recursive function and its arguments
Two global variables are to be defined here, one to hold the single result that matches the condition and one to hold the set of results that match the condition.
There must be two parameters in the function, and since it takes k numbers from the set n, n and k are two int-type parameters.
Then there is one more parameter, the int variable startIndex, which is used to keep track of where in this level of recursion the set is traversed from (the set is [1,.... ,n]). - Backtracking function termination conditions
When did it reach the so-called leaf node?
If the size of the array path reaches k, it means that we have found a combination with a subset size of k. In the graph path stores the path from the root node to the leaf nodes. - The process of single-level search
The search process of the backtracking method is a tree structure traversal process, in the following figure, it can be seen that the for loop is used to traverse horizontally, and the recursive process is vertical traversal.
The for loop traverses each time starting from startIndex and then saves the fetched node i with path.
Upper code (●'◡'●)
class Solution {
private:
vector<vector<int>> result; // Holds the set of results that match the conditions
vector<int> path; // Used to store eligible results
void backtracking(int n, int k, int startIndex) {
if (() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i); // processing node
backtracking(n, k, i + 1); // recursive (calculation)
path.pop_back(); // look back upon，Undo processing of nodes
}
}
public:
vector<vector<int>> combine(int n, int k) {
(); // You can leave it out.
(); // You can leave it out.
backtracking(n, k, 1);
return result;
}
};
Combinatorial problems are classic problems solved by the backtracking method, we started by giving you a very visual example of a direct idea that requires 50 layers of for loops if n is 100 and k is 50.
This leads to the fact that backtracking is the solution to this problem of nested k-level for loops.
The search process of the backtracking method is then further abstracted into a tree structure, which can be visualized.
This is followed by a step-by-step analysis of function parameters, termination conditions, and single-level searches using a three-part backtracking method.
optimize
To give an example, if n = 4 and k = 4, then at the first level of the for loop, traversals from element 2 are meaningless. At the second level of the for loop, traversals from element 3 are meaningless.
As shown in the figure, this optimization is like cutting off excess branches from a recursive tree
Each node in the graph (the graph is a rectangle), on behalf of this layer of a for loop, then each layer of the for loop from the second number to start traversing the words, are meaningless, are invalid traversal.
So, the place where you can prune is at the starting position chosen by the for loop at each level of the recursion.
If the number of elements after the start of the for loop is less than the number of elements we need, then there is no need to search.
Next look at the optimization process as follows:
- Number of elements already selected: ().
- The number of elements still required is: k - (); the
- Traverse through the set n at most from that starting position : n - (k - ()) + 1, starting with
Optimize code (●ˇ∀ˇ●)
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - ()) + 1; i++) { // Where to optimize
path.push_back(i); // processing node
backtracking(n, k, i + 1);
path.pop_back(); // look back upon，Undo processing of nodes
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
It's not easy to write a blog, so please give me some support 8~!