\(S_{N,M}\) を長さ \(N\) かつ全ての要素が \(1\) 以上 \(M\) 以下の狭義単調増加である整数列の集合とします。

まず、\(N=1\) であるとき \(S_{N,M}=(\{1\},\{2\},\dots,\{M\})\) です。

以降、\(N \ge 2\) とします。 \(S_{N,M}\) に含まれる整数列の最後の項を全探索します。

もし最後の項が \(K\) であるならば始めの \(N-1\) 項としてあり得るものの集合は \(S_{N-1,K-1}\) に等しいです。ここで、\(N-1 \le K-1\) でなければならないことに注意してください。

より、\(K\) を全探索し \(S_{N-1,K-1}\) の要素に \(K\) を付け加えたものを \(S_{N,M}\) に加えることで \(S_{N,M}\) を求めることができます。

より、この問題を解くことができます。

また、別解法として C++ であれば \(0\) が \(N\) 個、\(1\) が \(M-N\) 個この順で並べられた vector を用意し、next_permutation で毎回 \(0\) である要素の index を出力することによっても解くことができます。こちらの解法の方が実装は短く済みます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dp[10][10];
void solve(int n,int m){
  if(dp[n][m].size()) return;
  if(n==1){
    for(int i=1;i<=m;i++){
      dp[n][m].push_back({i});
    }
  }
  else{
    for(int k=1;k<=m;k++){
      if(n-1<=k-1){
        solve(n-1,k-1);
        for(int i=0;i<dp[n-1][k-1].size();i++){
          vector<int> a=dp[n-1][k-1][i];
          a.push_back(k);
          dp[n][m].push_back(a);
        }
      }
    }
  }
}
int main() {
  int n,m;
  cin>>n>>m;
  solve(n,m);
  sort(dp[n][m].begin(),dp[n][m].end());
  for(int i=0;i<dp[n][m].size();i++){
    for(int j=0;j<n;j++) cout<<dp[n][m][i][j]<<" ";
    cout<<endl;
  }
}

実装例(next_permutation,C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,m;
  cin>>n>>m;
  vector<int> a;
  for(int i=0;i<n;i++) a.push_back(0);
  for(int i=0;i<m-n;i++) a.push_back(1);
  do{
    for(int i=0;i<m;i++){
      if(a[i]==0) cout<<i+1<<" ";
    }
    cout<<endl;
  }while(next_permutation(a.begin(),a.end()));
}