Generate All Distinct Subsequences of Length m from Numbers 1 to n with Repetitions

Given two numbers n and m, generate all distinct subsequences of length m using numbers from 1 to n. You may repeat a number.

INPUT: n=5, groups=3
OUTPUT: 1,1,3
	1,2,2
	1,3,1
	2,1,2
	2,2,1
	3,1,1

INPUT: n=7, groups=3
OUTPUT: 1,1,5
	1,2,4
	1,3,3
	1,4,2
	1,5,1
	2,1,4
	2,2,3
	2,3,2
	2,4,1
	3,1,3
	3,2,2
	3,3,1
	4,1,2
	4,2,1
	5,1,1

APPROACH: We need to generate all subsequences that sums up to n and are of length m.

1. Initialize a vector of vector to store all sequences and a vector which will have current subsequence.
2. Create a vector of integer having number from 1 to n.
3. Traverse the vector and generate all sequences.
4. Add the current vector digit to the current subsequence and traverse the remaining elements to generate all subsequences.
5. After generating the subsequence with current digit, remove that digit from the current subsequence.

Implementation:

// This code is contributed by Manu Pathria
#include <bits/stdc++.h>
using namespace std;

vector<int> combination;
vector<vector<int>> combinations;

void explore(vector<int>& candidates, int target) {
    if (target == 0) {
        combinations.push_back(combination);
        return;
    }
    if (target < 0) return;

    for (int i = 0; i < candidates.size(); i++) {
        combination.push_back(candidates[i]);
        explore(candidates, target - candidates[i]);
        combination.pop_back();
    }
}

int main() {
    vector<int> arr;
    int n = 7, groups = 3;

    for (int i = 1; i <= n; i++) {
        arr.push_back(i);
    }

    explore(arr, n);

    for (int i = 0; i < combinations.size(); i++) {
        if (combinations[i].size() == groups) {
            for (int j = 0; j < combinations[i].size(); j++) {
                if (j == combinations[i].size() - 1) {
                    cout << combinations[i][j];
                } else {
                    cout << combinations[i][j] << ",";
                }
            }
            cout << endl;
        }
    }
    return 0;
}

Output:

1,1,5
1,2,4
1,3,3
1,4,2
1,5,1
2,1,4
2,2,3
2,3,2
2,4,1
3,1,3
3,2,2
3,3,1
4,1,2
4,2,1
5,1,1