[Recursive] Subset Full Permutation and Combination Problem

1.1 Subset I

The idea can be simply summarized as a binary tree. Each bifurcation either selects an element or selects nothing. There are n times in total, so n + 1 is used to save the result and return. like this:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int>temp;
vector<vector<int> > result;
void DFS(int m){
    if (m == n + 1){
        result.push_back(temp);
        return ;
    }

    //Select element m
    temp.push_back(m);
    DFS(m + 1);//continue recursion
    temp.pop_back();//return
    //select empty
    DFS(m + 1);
}

bool cmp(vector<int > & amp;a,vector<int > & amp;b){
    if (a.size()!=b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    
    scanf("%d", & amp;n);
    DFS(1);
    sort(result.begin(),result.end(),cmp);
    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;
}

Finally, write your own comparison function. To put it simply, when the vector sizes are the same, you can directly compare them according to the < > comparison symbols. When the sizes are different, they are sorted according to the vector size. Here, according to the question requirements, they are all less than.

1.2 Subset II

The difference is that you give some elements and sort them yourself.

Then you only need to use an array to store these elements, and when pushing/popping the stack, replace them with the corresponding array elements. The idea is the same.

The code has barely changed.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> temp;
vector<vector<int> > result;
const int N =15;
int q[N];
int n;
void DFS(int m){
    if (m==n + 1){
        result.push_back(temp);
        return ;
    }
    temp.push_back(q[m]);
    DFS(m + 1);
    temp.pop_back();
    DFS(m + 1);
}
bool cmp(vector<int> & amp;a ,vector<int> & amp;b){
    if (a.size()!= b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    
    scanf("%d", & amp;n);
    for (int i=1;i<=n;i + + )scanf("%d", & amp;q[i]);
    DFS(1);
    sort(result.begin(),result.end(),cmp);

    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

1.3 Subset III

The idea is still binary tree deep search recursion, but due to repeated numbers, some values will be output repeatedly according to the previous output. For example, a subset of 1 in the example will output both sides, because the code does not consider the first 1 and the second Each 1 is different.

First the input sequence is in ascending order, so we can process these repeated elements consecutively.

For example 2 3 3 3 5

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> temp;
vector<vector<int> > result;
const int N =15;
int q[N];
int n;
void DFS(int idx){
    if (idx==n + 1){
        result.push_back(temp);
        return ;
    }
    int cnt=1;
    while (idx<n & amp; & amp; q[idx]==q[idx + 1]){
        cnt + + ;
        idx++;
    }//After this loop, idx = the serial number of the last repeated element, cnt is the number of repeated elements

    // select empty
    DFS(idx + 1);
    //select duplicate elements
    for (int i=1;i<=cnt;i + + ){
        temp.push_back(q[idx]);
        DFS(idx + 1);//Select duplicate elements as 1 2 3 ....cnt
    }
    //In this loop, we remove the elements previously added to temp one by one,
    //To backtrack to a situation where these repeated elements are not added
    for (int i=1;i<=cnt;i + + ){
        temp.pop_back();
    }
}
bool cmp(vector<int> & amp;a ,vector<int> & amp;b){
    if (a.size()!= b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    
    scanf("%d", & amp;n);
    for (int i=1;i<=n;i + + )scanf("%d", & amp;q[i]);
    DFS(1);
    sort(result.begin(),result.end(),cmp);

    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

2.1 Full arrangement I

The idea is very simple, here is a picture:

Set a q[] to indicate whether it has been used, recurse in sequence, and assign a value of 0 when returning;

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> temp;
vector<vector<int> > result;
int n;
const int N = 10;
int q[N]={0};
void DFS(int m){
    if (m == n + 1){
        result.push_back(temp);
    }
    for (int i=1;i<=n;i + + ){
        if (!q[i]){
            temp.push_back(i);
            q[i]=1;
            DFS(m + 1);
            q[i]=0;
            temp.pop_back();
        }

    }

}
bool cmp(vector<int> & amp;a ,vector<int> & amp;b){
    if (a.size()!=a.size())return a.size()<b.size();
    return a<b;
}
int main(){

    scanf("%d", & amp;n);
    DFS(1);
    sort(result.begin(),result.end(),cmp);
    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

2.2 Full Arrangement II

The idea is still simple. The full arrangement I uses i as a positive integer. This time, a given positive integer is pushed and popped from the stack. q[] is used to store the input number, and flag[] is used to indicate whether it has been used. The code is the same.

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
int n;
const int N=10;
int q[N];
int flag[N] = {0};
vector<int> temp;
vector<vector<int> > result;
void DFS(int m){
    if (m==n + 1){
        result.push_back(temp);
    }
    for (int i=1;i<=n;i + + ){
        if (!flag[i]){
            temp.push_back(q[i]);
            flag[i]=1;
            DFS(m + 1);
            flag[i]=0;
            temp.pop_back();
        }
    }

}
bool cmp(vector<int> & amp;a,vector<int> & amp;b){
    if (a.size()!=b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    scanf("%d", & amp;n);
    for (int i=1;i<=n;i + + )scanf("%d", & amp;q[i]);
    DFS(1);
    sort(result.begin(),result.end(),cmp);
    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

2.3 Full Arrangement III

If you follow the previous idea, there will be a lot of repetitions in Sample 1, which is similar to the solution of the subset, but here the number of each number is recorded, cnt[] is used for calculation, and each number is only recorded once;

1 1 3: Only take the last repeated id to record the number of times, like this: cnt[1] = 0 cnt[2]=2 cnt[3] =1

Then the full permutation is very simple. Each full permutation can only use cnt[i] times for the number q[i].

Then each for loop

 for (int i=1;i<=n;i + + ){
        if (cnt[i]){
            temp.push_back(q[i]);
            cnt[i]--;
            DFS(m + 1);
            cnt[i] + + ;
            temp.pop_back();
        }
    }

Only repeated values can be used once

#include 
#include 
#include 

using namespace std;
int n;
const int N = 10;
int q[N];
int cnt[N]={0};
vector temp;
vector >result;
void DFS(int m){
    if (m==n + 1){
        result.push_back(temp);
        return ;
    }
    for (int i=1;i<=n;i + + ){
        if (cnt[i]){
            temp.push_back(q[i]);
            cnt[i]--;
            DFS(m + 1);
            cnt[i] + + ;
            temp.pop_back();
        }
    }
}
bool cmp(vector & amp;a,vector & amp;b){
    if (a.size()!=b.size())return a.size()
3.1 Combination I
 

It is very similar to the full arrangement, but the full arrangement is in order (in the example, 3 4 and 4 3 are both valid in the full arrangement), while the combination is unordered, so we can artificially order it when selecting. Limit so there is no duplication.
The idea is similar to this recursion question
[Recursion] Number of solutions for decomposition of natural numbers_Mumei^'s blog-CSDN blog
We ensure that the latter number is greater than the previous requirement, then the combination problem can be achieved.
In Example 2, the two numbers x y satisfy (x
Then our DFS (int m), m is the sequence number that the following number needs to be greater than
DFS(0) can be used as an entry point
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
int n,k;
const int N = 15;


vector<int> temp;
vector<vector<int> > result;

void DFS(int m){
    if (temp.size()==k){//The recursive exit is changed to vector <int> the size of temp==k
        result.push_back(temp);
        return ;
    }
    for (int i=m + 1;i<=n;i + + ){
        //The loop starts from sequence number m + 1
        temp.push_back(i);
        DFS(i);//Use i as a parameter for the next recursion
        temp.pop_back();
    }
    return ;

}
bool cmp(vector<int> & amp;a,vector<int> & amp;b){
    if (a.size()!=b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    scanf("%d%d", & amp;n, & amp;k);
    DFS(0);
    sort(result.begin(),result.end(),cmp);
    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

 3.2 Combination II 
You need to enter the sequence yourself, the idea remains the same

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
int n,k;
const int N = 15;
int q[N];
vector<int> temp;
vector<vector<int> > result;

void DFS(int m){
    if (temp.size()==k){
        result.push_back(temp);
        return ;
    }
    for (int i=m + 1;i<=n;i + + ){
        temp.push_back(q[i]);
        DFS(i);
        temp.pop_back();
    }
}
bool cmp(vector<int> & amp;a,vector<int> & amp;b){
    if (a.size()!=b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    scanf("%d%d", & amp;n, & amp;k);
    for (int i=1;i<=n;i + + )scanf("%d", & amp;q[i]);

    DFS(0);
    sort(result.begin(),result.end(),cmp);
    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

3.3 Combination III

 You can learn from the idea of full arrangement and use cnt to count.
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
int n,k;
const int N = 15;
int q[N];
int cnt[N]={0};
vector<int> temp;
vector<vector<int> > result;

void DFS(int m){
    if (temp.size()==k){
        result.push_back(temp);
        return ;
    }
    for (int i=m;i<=n;i + + ){//i starts from m because there are repeated elements.
        if (cnt[i]){
            cnt[i]--;
            temp.push_back(q[i]);
            DFS(i);
            cnt[i] + + ;
            temp.pop_back();
        }
    }
}
bool cmp(vector<int> & amp;a,vector<int> & amp;b){
    if (a.size()!=b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    scanf("%d%d", & amp;n, & amp;k);
    for (int i=1;i<=n;i + + )scanf("%d", & amp;q[i]);
    for (int i=1;i<=n;i + + ){
        int j = i;
        cnt[i] = 1;
        while ((j + 1)<=n & amp; & amp;q[j]==q[j + 1]){
            cnt[i] + + ;
            j + + ;
        }
        i = j;
    }

    DFS(0);
    sort(result.begin(),result.end(),cmp);
    for (int i=0;i<result.size();i + + ){
        for (int j=0;j<result[i].size();j + + ){
            if (j==result[i].size()-1)printf("%d",result[i][j]);
            else printf("%d ",result[i][j]);
        }
        printf("\\
");
    }
    return 0;

}

However, what is different from the previous two combinations is that
for (int i=m + 1;i<=n;i + + ){<!-- -->
The condition is changed to
for (int i=m;i<=n;i + + ){<!-- -->
 If not, the previous sequence has no repeated elements, so the next sequence number needs to be + 1 to ensure that it is greater than the previous number. However, there are repeated elements here, so it starts from m.