C++: How to Generate All Combinations of a Vector of Digits of Length N, disregarding order?

Question

So I need to combine a specific number (not string) of digits from a vector of possible ones (all 0-9, not characters) in an N-digit number (not binary, then). However, I cannot have any extra permutations appear: for example 1234, 4321, 3124... are now the same and cannot be all outputed. Only one can be. This is hard because other questions cover these permutions by using std::next_permutation, but I still need the different combinations. My attempts at trying to remove permutations have failed, so how do you do this? Here is my current code with comments:

#include <iostream>
#include <vector>
using namespace std;
#define ll long long

int n = 0, m = 0, temp; //n is number of available digits
//m is the length of the desired numbers
//temp is used to cin
vector <int> given;
//vector of digits that can be used
vector <int> num;
//the vector to contain a created valid number
void generate(vector <int> vec, int m) {
    //recursive function to generate all numbers
    if (m == 0) {
        for (int x : num) {
            cout << x;
        }
        cout << '\n';
        return;
    }
    for (int i = 0; i < given.size(); i++) {
        num.push_back(given[i]); //add digit to number
        int save = given[i];
        given.erase(given.begin() + i);
        //no repeating digits, save the used one and delete
        //however, permutations can still pass, which is undesirable
        generate(vec, m - 1);
        //recursive
        num.pop_back();
        //undo move
        given.insert(given.begin() + i, save);
        //redo insert deleted digit
    }
}
int main () {
    cin >> n;
    //input number of available digits
    for (int i = 0; i < n; i++) {
        cin >> temp;
        given.push_back(temp); //input digits
    }
    cin >> m;
    //input length of valid numbers
    generate(given, m); //start recursive generation function
    return 0;
}

I tried deleting permutations before printing them and erasing more digits to stop generating permutations, but they all failed. Lots of other questions still used std::next_permutation, which was not helpful.

Answer 1

Unlike some people who suggested binary strings in some comments, you can begin by having a recursive function that can go two ways as an on/off switch to decide whether or not to include a given digit. I personally like using a recursive function to do this and a check for length at the end to actually print the number of the desired len, demonstrated in the code below:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int givencount = 0, temp = 0, len = 0;
vector <int> given;
string creatednum;
void generate(int m) {
    if (m == givencount) {
        if (creatednum.length() == len) {
            cout << creatednum << '\n';
        }
        return;
    }
    for (int i = 0; i < 2; i++) {
        if (i == 1) {
            generate(m + 1);
            continue;
        }
        creatednum = creatednum + ((char) ('0' + given[m]));
        generate(m + 1);
        creatednum.erase(creatednum.begin() + creatednum.length() - 1);
    }
}
int main () {
    cin >> givencount;
    for (int i = 0; i < givencount; i++) {
        cin >> temp;
        given.push_back(temp);
    }
    cin >> len;
    generate(0);
    return 0;
}