aoj0507:Square

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0507

解法

再帰で解きました。出来るだけ縦に高く積めるものを優先し、なおかつ前に選んだものよりも低くなるようにしていく。残り0個になったら出力。

コード

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

int N;
void dfs(int rest,int prev,vector<int>&vec){
    if(rest==0){
        for(int i=0;i<vec.size();i++){
            if(i)cout<<" ";
            cout<<vec[i];
        }
        cout<<endl;
        return;
    }
    for(int i=min(rest,prev);i>0;i--){
        vec.push_back(i);
        dfs(rest-i,i,vec);
        vec.pop_back();
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    while(cin>>N,N){
        vector<int>step;
        dfs(N,N,step);
    }
}