题目链接



dfs，转化为处理子问题如123456，1和子问题“23456”，12和子问题“3456”等

注意遇到重复的切割方式不能简单的修改ans=-2，因为当再次遇到相同方式，会覆盖掉-2.

import java.util.*;public class Main {public static int ans=-1;//如果此值未修改，则输出errorpublic static boolean flag=false;//标记是否出现了重复的切割方案public static LinkedList<Integer> tmp=new LinkedList<Integer>();public static LinkedList<Integer> ANS;public static void dfs(String x,int curSum,int target) {//当前在处理子串xif(curSum>target) {return;}if(x.equals("")) {//已经切割完毕if(curSum>ans) {flag=false;ans=curSum;ANS=new LinkedList<Integer>(tmp);}else if(curSum==ans) {//ans=-2;//表示遇到相同的切割方式了,不能用这种方式，如果存在3、5等等奇数种这种分割方式，会抵消flag=true;}return;}int sum=0;for(int i=0;i<x.length();i++) {sum=sum*10+x.charAt(i)-'0';tmp.addLast(sum);dfs(x.substring(i+1, x.length()),curSum+sum,target);tmp.removeLast();}}public static void main(String[] Args) {Scanner sc=new Scanner(System.in);String[] str=new String[2];while(sc.hasNextLine()) {//一行一行读进来String tmp=sc.nextLine();str=tmp.split(" ");if(str[0].equals(str[1]) && str[0].equals("0")) {break;}ans=-1;int target=Integer.parseInt(str[0]);dfs(str[1],0,target);if(ans==-1) {System.out.println("error");}else if(flag) {System.out.println("rejected");}else {System.out.print(ans+" ");for(int i=0;i<ANS.size();i++) {System.out.print(ANS.get(i)+" ");}System.out.println();}}}
}