DFS（全排列）--相同序号不能相邻

小多想在美化一下自己的庄园。他的庄园毗邻一条小河，他希望在河边种一排树，共 M 棵。小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。

输入描述:

第一行包含一个正整数 N，表示树的品种数量。 第二行包含 N 个正整数，第 i (1 <= i <= N) 个数表示第 i 个品种的树的数量。 数据范围： 1 <= N <= 1000 1 <= M <= 2000

输出描述:

输出一行，包含 M 个正整数，分别表示第 i 棵树的品种编号 (品种编号从1到 N)。若存在多种可行方案，则输出字典序最小的方案。若不存在满足条件的方案，则输出"-"。

示例1

输入

3 4 2 1

输出

1 2 1 2 1 3 1

#include <iostream>
#include <vector>
using namespace std;

bool dfs(vector<int>& a,vector<int>& b,int num,int Pre){
    if(num == 0){
        return true;
    }
    for(int i = 1;i <= a.size();i ++){
        if(a[i] > (num / 2 + 1)){
            return false;
        }
        if(a[i] > 0 && i != Pre){
            a[i] --;
            num --;
            b.push_back(i);
            if(dfs(a,b,num,i)){return true;}
            b.pop_back();
            num ++;
            a[i] ++;
        }
    }
    return false;
}

int main(){
    int N;
    scanf("%d",&N);
    vector<int> a(N + 1);
    int num = 0;
    for(int i = 1;i <= N;i ++){
        scanf("%d",&a[i]);
        num += a[i];
    }
    vector<int> Result;
    if(dfs(a,Result,num,0)){
        for(int i = 0;i < Result.size() - 1;i ++){
            printf("%d ",Result[i]);
        }
        printf("%d\n",Result[Result.size() - 1]);
    }
    else{
        printf("-\n");
    }
    return 0;
}