题解 P1157 【组合的输出】

ICE_Wol · 2018-05-17 23:15:36 · 题解

其实本题递归深搜可以轻松解决问题

但无奈题干不允许使用递归

所以以下给出非递归解法

具体解析参见代码注释

整份代码的核心在于第32行的判断条件,务必要注意

#include<iostream>
#include<iomanip>
using namespace std;
int a[1005],n,m,arr = 1;
int main()
{
    cin >> n >> m;
    while(arr){
        if(arr >= m + 1){                   //达到边界时打印解
            for(int i = 1;i <= m;i++)
                cout << setw(3) << a[i];     //注意场宽设置
            cout << endl;
            arr--;                         //回溯到前一位
            continue;
        }
        if(!a[arr]){                         //若该位置为空
            a[arr] = a[arr - 1] + 1;         //在其前一位基础上加一
            arr ++;
            continue;
        }
        if(a[arr] + m - arr < n){           //**关键** 判定在当前位为a[arr]的情况下向后推(m - arr)位是否超出题目的最大数字限制
            a[arr++] ++;                     //当前位自加后挪至后一位  
            continue;
        }
        a[arr--] = 0;                       //将当前位归零,回溯至前一位
    }
    return 0;
}