src/math/next_combination.hpp

View this file on GitHub
Last update: 2026-01-30 22:16:29+09:00
Include: #include "src/math/next_combination.hpp"

Depends on

src/template.hpp

Code

#include "../template.hpp"

bool next_combination(vector<int>& a,int n){
    int r=si(a);
    int i=r-1;
    while(~i&&a[i]==i+n-r) i--;
    if(i==-1) return false;
    a[i]++;
    for(int j=i+1;j<r;j++) a[j]=a[j-1]+1;
    return true;
}
bool next_combination_with_replacement(vector<int>& a,int n){
    int r=si(a);
    for(int i=r;i--;){
        if(a[i]<n-1){
            ++a[i];
            for(int j=i+1;j<r;j++) a[j]=a[i];
            return true;
        }
    }
    return false;
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/math/next_combination.hpp"

bool next_combination(vector<int>& a,int n){
    int r=si(a);
    int i=r-1;
    while(~i&&a[i]==i+n-r) i--;
    if(i==-1) return false;
    a[i]++;
    for(int j=i+1;j<r;j++) a[j]=a[j-1]+1;
    return true;
}
bool next_combination_with_replacement(vector<int>& a,int n){
    int r=si(a);
    for(int i=r;i--;){
        if(a[i]<n-1){
            ++a[i];
            for(int j=i+1;j<r;j++) a[j]=a[i];
            return true;
        }
    }
    return false;
}