Directory
Foreword:
78. Subset
Title description:
Input and output description:
Thoughts and ideas:
90. Subset II
Title description:
Input and output description:
Thoughts and ideas:
491. Incrementing Subsequences
Title description:
Input and output description:
Thoughts and ideas:
Foreword:
If the subset problem, combination problem, and segmentation problem are all abstracted into a tree, then the combination problem and the segmentation problem are to collect the leaf nodes of the tree, and the subset problem is to find all the nodes of the tree!
The subset is unordered, and the fetched elements will not be fetched repeatedly. When writing the backtracking algorithm, for must start from Index.
There are two types of issues to be discussed:
- There are no repeated elements in the set
- There are repeated elements in the set, and the obtained subset needs to be deduplicated (sortable)
- Find increasing subsets in a set (not sortable)
78. Subset
Description of topic:
You are given an array nums of integers where the elements are distinct. Returns all possible subsets (power sets) of this array.
Solution sets cannot contain duplicate subsets. You can return solution sets in arbitrary order.
Input and output description:
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1, 2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Tip:
- 1 <= nums. length <= 10
- -10 <= nums[i] <= 10
- All elements in nums are distinct from each other
Thoughts and ideas:
This question is a template question. From this question, you can feel that the solution to the subset problem is different from the previous one.
#include <bits/stdc++.h>
using namespace std;
/*
* Author: Xixi Wuli
* 78. Subset
* */
vector<vector<int>> result;
vector<int> path;
/*
* Function: backtracing()
* Input parameters: s: input string index: array element subscript
* */
void backtracing(vector<int> & amp;nums,int Index){
result. push_back(path);
//backtracking process
for (int i = Index; i < nums. size(); + + i) {
path.push_back(nums[i]);
backtracing(nums, i + 1);
path. pop_back();
}
};
int main() {
result. clear();
path. clear();
int num;
vector<int> nums;
while(cin>>num){
nums.push_back(num);
if(getchar() == '\
'){
break;
}
}
backtracing(nums,0);
cout << "[";
for (int i = 0; i < result. size(); + + i) {
cout << "[";
for (int j = 0; j < result[i]. size(); + + j) {
cout<<result[i][j];
if(j != result[i].size() - 1) cout << ",";
}
cout << "]";
if(i != result. size() - 1) {cout << ",";}
}
cout << "]";
return 0;
}
/* test example
1 2 3
0
*
* */
90. Subset II
Description of topic:
Given an integer array nums , which may contain repeated elements, please return all possible subsets (power sets) of the array.
Solution sets cannot contain duplicate subsets. In the returned solution set, subsets can be arranged in arbitrary order.
Input and output description:
Example 1:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Tip:
- 1 <= nums. length <= 10
- -10 <= nums[i] <= 10
Thoughts and ideas:
The difference between this question and the previous question: there are repeated elements in the set, and the obtained subset needs to be deduplicated.
Therefore, on the basis of the previous question, introduce tree layer deduplication. For this question, you can refer to 40. Combination sum II in the combination problem in the backtracking algorithm.
#include <bits/stdc++.h>
using namespace std;
/*
* Author: Xixi Wuli
* 90. Subset II
* */
vector<vector<int>> result;
vector<int> path;
/*
* Function: backtracing()
* Input parameters: s: input string index: array element subscript used: used flag
* */
void backtracing(vector<int> & amp;nums,int Index, vector<bool> used){
result. push_back(path);
//backtracking process
for (int i = Index; i < nums. size(); + + i) {
// used[i - 1] == true, indicating that the same branch nums[i - 1] has been used
// used[i - 1] == false, indicating that the same tree layer nums[i - 1] has been used
// Here, pay attention to the difference between the tree layer and the branches, here we are skipping the tree layer.
if(i > 0 & amp; & amp; nums[i] == nums[i - 1] & amp; & amp; used[i - 1] == false){
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracing(nums, i + 1, used);
used[i] = false;
path. pop_back();
}
};
int main() {
result. clear();
path. clear();
int num;
vector<int> nums;
while(cin>>num){
nums.push_back(num);
if(getchar() == '\
'){
break;
}
}
vector<bool> used(nums. size(), false);
sort(nums.begin(),nums.end());
backtracing(nums,0,used);
// output mode
cout << "[";
for (int i = 0; i < result. size(); + + i) {
cout << "[";
for (int j = 0; j < result[i]. size(); + + j) {
cout<<result[i][j];
if(j != result[i].size() - 1) cout << ",";
}
cout << "]";
if(i != result. size() - 1) {cout << ",";}
}
cout << "]";
return 0;
}
/* test example
1 2 2
0
*
* */
491. Incrementing subsequence
Description of topic:
Given an array of integers nums , find and return all distinct increasing subsequences of that array that have at least two elements . You can return answers in any order.
An array may contain repeated elements, such as two integers being equal, can also be regarded as a special case of an increasing sequence.
Input and output description:
Example 1:
Input: nums = [4,6,7,7] Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7] ,7],[6,7],[6,7,7],[7,7]]
Example 2:
Input: nums = [4,4,3,2,1] Output: [[4,4]]
Tip:
- 1 <= nums. length <= 15
- -100 <= nums[i] <= 100
Thoughts and ideas:
What is the difference between this question and the previous question Subset II? This question is to find different increasing subsequences in the array, so the original array cannot be sorted.
Therefore, the original logic cannot be used for the method of deduplication. This topic is still deduplication at the tree level, which is implemented here using set.
#include <bits/stdc++.h>
using namespace std;
/*
* Author: Xixi Wuli
* 491. Incrementing Subsequence
* */
vector<vector<int>> result;
vector<int> path;
/*
* Function: backtracing()
* Input parameters: s: input string index: array element subscript
* */
void backtracing(vector<int> & amp;nums,int Index){
if(path. size() > 1){
result. push_back(path);
}
//backtracking process
unordered_set<int> uset; //Use set to deduplicate the elements of this layer, and the new layer will redefine the empty
for (int i = Index; i < nums. size(); + + i) {
if((!path.empty() & amp; & amp; nums[i] < path.back()) || uset.find(nums[i]) != uset.end()){
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracing(nums, i + 1);
path. pop_back();
}
};
int main() {
result. clear();
path. clear();
int num;
vector<int> nums;
while(cin>>num){
nums.push_back(num);
if(getchar() == '\
'){
break;
}
}
backtracing(nums,0);
// output mode
cout << "[";
for (int i = 0; i < result. size(); + + i) {
cout << "[";
for (int j = 0; j < result[i]. size(); + + j) {
cout<<result[i][j];
if(j != result[i].size() - 1) cout << ",";
}
cout << "]";
if(i != result. size() - 1) {cout << ",";}
}
cout << "]";
return 0;
}
/* test example
4 6 7 7
4 4 3 2 1
*
* */
The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treehome page overview 50392 people are learning systematically