全排列代码问题

a327904410

问题描述
　　给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
　　例如:
　　3 1 2 4
　　4 3 6
　　7 9
　　16
　　现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
输入格式
　　第1行为两个正整数n，sum
输出格式
　　一个1～N的一个排列
样例输入
4 16
样例输出
3 1 2 4

帮我看下代码为什么输出不是最小字典序，在十次测试中两个出现问题，不知道为什么，求大佬帮我看看哪里出了问题

#include<stdio.h>
#include<string.h>

// a[]是原数组，b[]是计算并判断是否等于sum，c[]保存最小字典排序
// n是数组长度，sum是数组里的数累加后的最终结果
// flag 一是判断有没有能计算出sum的数组，二是保存第一个数组c[]
int a[11], b[11], c[11], n, sum, flag = 1;

void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
}

void perm(int a[], int l, int r) {
        int i, j;
        if (l == r) {    // 排完序
                for (i = 0; i < n; i++) {  // 将a[]复制进b[]
                        b[i] = a[i];
                }
                j = n;   // j表示b[]数组计算长度，长度递减
                while (j) {
                        for (i = 1; i < j; i++) {
                                b[i - 1] += b[i];
                        }
                        j--;
                }
                if (b[0] == sum) {    // 如果最终计算出等于sum
                        if (flag) {       // 将第一次得到的数组保存在c[]
                                for (i = 0; i < n; i++) {
                                        c[i] = a[i];
                                }
                                flag = 0;
                        }
                        else {       // 第二次得到能计算出sum的数组
                                int ret = memcmp(a, c, n);    // 比较大小，取最小数组
                                if (ret < 0) {
                                        for (i = 0; i < n; i++) {
                                                c[i] = a[i];    // 最小数组给c[]
                                        }
                                }
                        }
                        
                }
        }
        else {
                for (i = l; i <= r; i++) {   // 全排列，递归
                        swap(a, l, i);
                        perm(a, l + 1, r);
                        swap(a, l, i);
                }
        }
}

int main() {
        scanf("%d%d", &n, &sum);
        int i;
        for (i = 0; i < n; i++) {
                a[i] = i + 1;
        }
        perm(a, 0, n - 1);
        if (flag) {    // 若没找到数组，则返回空
                printf("");
        }
        else {
                for (i = 0; i < n; i++) {
                        printf("%d ", c[i]);
                }
        }
        return 0;
}

input6.txt (6 Bytes, 下载次数: 1)

2022-3-28 23:50 上传

点击文件名下载附件

output6.txt (18 Bytes, 下载次数: 0)

2022-3-28 23:50 上传

点击文件名下载附件

a327904410

代码可能有点混乱，没整理好，不要见怪

a327904410

我打印了a[]所有数组，发现有最小字典序的，但没能复制到c[]，不知道为啥

a327904410

放假回来看了下，问题已解决，貌似删不了帖子。