# Poj Solution 1416

```http://poj.org/problem?id=1416

/* @author: */
import java.util.*;
public class Main {
private int target;
private char num[];
private int max;
private StringBuffer s;
private StringBuffer result;
boolean check;

public Main(int target,char num[]){
this.target=target;
this.num=num;
max=0;
s=new StringBuffer("");
result=new StringBuffer("");
}

public boolean getCheck(){
return check;
}

public int getMax(){
return max;
}

public String getResult(){
return result.toString();
}

private boolean isOk(){
int sum=0;
for(int i=0;i< num.length;i++){
sum+=num[i]-'0';
}
if(sum>target) return false;
else return true;
}

void  dfs(int startIndex,int sumTotal){
int i,t=0;
if(startIndex==num.length)
{
if(sumTotal==max){
check=false;
}else if(sumTotal>max){
check=true;
max=sumTotal;
result=s;
}
}
for(i=1;i< num.length-startIndex+1;i++){
t*=10;
t+=num[startIndex+i-1]-'0';
if(t+sumTotal>target)
return;
StringBuffer tt=new StringBuffer(s);
s.append(Integer.toString(t)).append(" ");

dfs(startIndex+i,sumTotal+t);
s=tt;
}
}

public static void main(String args[]){
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{

int target=sc.nextInt();
char num[]=sc.next().toCharArray();
if(target==0)
break;
Main m=new Main(target,num);
if(!m.isOk())
System.out.printf("errorn");
else{
m.dfs(0,0);
if(!m.getCheck())
System.out.printf("rejectedn");
else{
System.out.print(m.getMax()+" ");
System.out.println(m.getResult());
}

}

}
}
}

```
This entry was posted in poj. Bookmark the permalink.