Other/EnumerateDivision.hpp

View this file on GitHub
Last update: 2023-04-05 23:10:22+09:00
Include: #include "Other/EnumerateDivision.hpp"
Link: https://atcoder.jp/contests/abc226/submissions/27125989

Code

/*
Nの分割方法の列挙
N=50 -> 200000 程度
verified : https://atcoder.jp/contests/abc226/submissions/27125989
*/
vector<vector<int>> enumerate_division(int N){
    vector<vector<int>> ret;
 
    function<void(vector<int>,int,int)> rec=[&](vector<int> v,int S,int K){
        if(S==0){
            ret.push_back(v);
            return ;
        }
 
        for(int t=min(S,K);t>0;t--){
            v.push_back(t);
            rec(v,S-t,t);
            v.pop_back();
        }
    };
    rec({},N,N);
    return ret;
}

#line 1 "Other/EnumerateDivision.hpp"
/*
Nの分割方法の列挙
N=50 -> 200000 程度
verified : https://atcoder.jp/contests/abc226/submissions/27125989
*/
vector<vector<int>> enumerate_division(int N){
    vector<vector<int>> ret;
 
    function<void(vector<int>,int,int)> rec=[&](vector<int> v,int S,int K){
        if(S==0){
            ret.push_back(v);
            return ;
        }
 
        for(int t=min(S,K);t>0;t--){
            v.push_back(t);
            rec(v,S-t,t);
            v.pop_back();
        }
    };
    rec({},N,N);
    return ret;
}