Generate all kinds of permutations and combinations using backtracking/recursion

There are four kinds of permutations or combinations possible based on whether repetition is allowed or not and whether order matters or not.
All four of them are summarized and explained by example in the below figure.

To generate them using recursion we make the recursion tree.

All the combinations in this tree are the first type of permutations(n^r). if the repetitions are not allowed but the order matters then you just skip the blue ones. the point to not here is that we skipped those items here which are same as the parent node like for 2's children we skipped when 2 2 came, for 3's children we skipped when 3 3 came. So this will take care of the repetitions thing. now if the order does not matter then we cant take both 1 2 and 2 1.In the figure we skip green ones. Notice here that we only skip the children elements who are less then the parent or you can say we take elements starting from the parent itself. for example, for 1's children we start taking elements from 1 , like 1 1 ,1 2 ,1 3 for 2's children we start taking elements from 2 , like 2 2, 2 3 and for 3's children we start taking elements from 3,like 3 3.
Based on following observations here is the Cpp code

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

void permComb(vector<int> data, int r, bool order, bool repeat, vector<int> out = {}, int i = 0, unordered_set<int> set = {})
{
    if (out.size() == r)
    {
        print(out);
        return;
    }

    for (int next = (order ? 0: i); next < data.size(); next++)
    {
        if (!repeat and set.find(data[next])!=set.end()) continue;
        set.insert(data[next]);     // to track repetitions
        out.push_back(data[next]);
        permComb(data, r, order, repeat, out, next, set);
        out.pop_back();
        set.erase(data[next]);
    }
    return;
}


int main()
{
    vector<int> data{ 1,2,3 };
    permComb(data, 3, true, false);
    return 0;
}

Update:

• I just realized using array to handle repetitions is more faster.
• If you want only the fourth type of combination (which is all subset) this code can be optimized by removing the unordered set and at each choice passing next+1 as parameter instead of next.(the reason can be found in the recursion tree for the fourth type).or It can also be solved by considering a different recursive tree approach which goes like should I consider the first element in or not and so on for all. this can also be solved by bit-masking.

• I started Learning Dynamic programming, And the first problem I encountered was 0-1 knapsack problem.in this problem we are given a bunch of items with values and associated weight and also given a knapsack of capacity W to put items into. And we need to find the maximum profit achieved by choosing items and putting it into knapsack. If you think about it this problem demands no order and no repetition which is type 4 (or subset) type problem. so this can be solved by backtracking also.

• If any problem you find is demanding any different type of permutations then first try to draw the recursive tree like the first type and then try to cross out the options which does not fit in your solutions and then try to augment that into the code snippet. For example, I was doing a letter tile possibilities problem on leetcode. which demanded that the certain characters can be used only fixed amount of times in a sequence. I solved it using the idea I got from the cross check method I described.

let me know your thoughts in the comments.👋