每日一道算法题数字游戏（蓝桥杯练习系统）全排列问题-创新互联

资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给定一个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
数据规模和约定
0解题思路:主要是1~N的整数要怎么排序才能符合这样加起来的和能为sum，这就用到了全排列，而且今天学到了怎么把把数组加成这种阶梯状的值，只要s[j]+=s[j+1]，然后总共加n-1次，每次加n-i次，i从1到n

import java.util.Arrays;
import java.util.Scanner;

public class Main{static int n=0;
    static int sum=0;
    static int[] used=new int[11];//用来标记是否使用
    static int[] dp=new int[11];//用来存储每个位置的数字
    public static void main(String[] args){Scanner in=new Scanner(System.in);
        n=in.nextInt();
        sum=in.nextInt();
        Arrays.fill(used,0);
        DFS(1);
    }
    public static void DFS(int step){if(step==n+1){//说明已经列满n个数了，这个时候需要判断和是否为sum
            int s[] =new int[n+1];//防止破坏dp数组里的数，因为如果满足条件需要输出dp数组的内容
            for(int i=1;i<=n;i++){s[i]=dp[i];
            }
            for(int i=1;i//总共加n-1次
                for(int j=1;j<=n-i;j++){//把数组的和全加到j=1的位置上去
                    s[j]+=s[j+1];
                }
            }
            if(s[1]==sum)//满足条件，输出
            {for(int i=1;i<=n;i++){System.out.print(dp[i]);
                    if(ireturn;
            }
        }
        for(int i=1;i<=n;i++){if(used[i]==0){used[i]=1;
                dp[step]=i;
                DFS(step+1);
                used[i]=0;
            }
        }
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧