Did you know that subset problems are actually template problems?

[[426614]]

After understanding the essence, this is a template question

Subset

Link to LeetCode questions: https://leetcode-cn.com/problems/subsets/

Given an integer array nums with no repeated elements, return all possible subsets (power sets) of the array.

Note: The solution set cannot contain repeated subsets.

Example:

Input: nums = [1,2,3]

Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

Ideas

The subset problem is different from 77. Combination and 131. Splitting palindrome strings.

If we abstract the subset problem, combination problem, and partition problem into a tree, then the combination problem and partition problem are to collect the leaf nodes of the tree, while the subset problem is to find all the nodes of the tree!

In fact, subset is also a combinatorial problem, because its set is unordered, the subset {1,2} and the subset {2,1} are the same.

Since it is unordered, the elements that have been taken will not be taken repeatedly. When writing the backtracking algorithm, for should start from startIndex instead of starting from 0!

Some students asked, when can for start from 0?

When solving permutation problems, we have to start from 0, because sets are ordered. {1, 2} and {2, 1} are two sets. We will talk about permutation problems in subsequent articles.

Taking nums = [1,2,3] in the example, we can abstract the subset into a tree structure as follows:

Subset

From the red line part in the figure, we can see that when traversing the tree, all the nodes are recorded, which is the required subset set.

Back to the trilogy

• Recursive function parameters

The global variable array path collects elements for the subset, and the two-dimensional array result stores the subset combinations. (It can also be put into the recursive function parameters)

The recursive function parameters are mentioned above, and startIndex is required.

The code is as follows:

 vector<vector< int >> result;
 vector< int > path;
 void backtracking(vector< int >& nums, int startIndex) {

Recursion termination condition

As can be seen from the figure:

Subset

When the remaining set is empty, it is a leaf node.

So when is the remaining set empty?

That is, startIndex is greater than the length of the array, so it terminates because there are no elements to be taken. The code is as follows:

 if (startIndex >= nums. size ()) {
 return ;
 }

In fact, there is no need to add a termination condition, because startIndex >= nums.size(), and the for loop at this level has already ended.

• Single-layer search logic

To find the subset problem, no pruning is required! Because the subset is to traverse the entire tree.

Then the single-layer recursive logic code is as follows:

 for ( int i = startIndex; i < nums. size (); i++) {
 path.push_back(nums[i]); // Subset collection elements
 backtracking(nums, i + 1); // Note that starting from i+1, elements are not repeated
 path.pop_back(); // backtracking
 }

C++ Code

According to the backtracking algorithm, you should know this! The backtracking algorithm template given is:

 void backtracking(parameters) {
 if (termination condition) {
 Store the results;
 return ;
 } 
 
 for (select: elements in the current layer set (the number of node children in the tree is the size of the set)) {
 Processing nodes;
 backtracking(path, selection list); // recursion
 Backtracking, undoing processing results
 }
 }

You can write the following backtracking algorithm C++ code:

 class Solution {
 private:
    vector<vector< int >> result;
 vector< int > path;
    void backtracking(vector< int >& nums, int startIndex) {
 result.push_back(path); // Collect subsets and put them above the one where the addition is terminated, otherwise you will miss yourself
 if (startIndex >= nums.size ()) { // The termination condition can be omitted
 return ;
 }
 for ( int i = startIndex; i < nums. size (); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
 path.pop_back();
 }
 }
 public :
    vector<vector< int >> subsets(vector< int >& nums) {
 result.clear();
 path.clear();
        backtracking(nums, 0);
 return result;
 }
 };

In the comments, you can see that you don't need to write the termination condition because we are going to traverse the entire tree.

Some students may worry about whether there will be infinite recursion if the termination condition is not written.

No, because the next layer of each recursion starts from i+1.

This article is reprinted from the WeChat public account "Code Random Thoughts", which can be followed through the following QR code. To reprint this article, please contact the Code Random Thoughts public account.