飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1347

易知对于3^i次方 3^0+3^1+....3^(i-1)<3^i 且对于k项，一共有2^k-1(不包括空集，对空集进行特殊处理) 所以当n==2^k-1时，则前k项都包括，当n>2^k-1&&n<2^(k+1)-1时，包含第k+1项，将n-(2^k-1)后就是k+1项的事情了，领n1=n-(2^k-1),

n2=n1-1时，此时k+1已经处理了，则n2又变为原来的n，进行递归求解。

import java.math.BigInteger;
import java.util.*;

public class Maintf {
	public static BigInteger fac[];
	public static ArrayList<Integer> al;
	public static void DFS(BigInteger x){
		if(x.compareTo(BigInteger.ZERO)==0)return;
		for(int i=1;i<64;i++){
			if(x.compareTo(fac[i])==0){
				for(int j=i;j>=1;j--){
					al.add(j);
				}
				return;
			}
			if(x.compareTo(fac[i])>0&&x.compareTo(fac[i+1])<0){
				x=x.subtract(fac[i]).subtract(BigInteger.ONE);
				al.add(i+1);
				DFS(x);
				return;
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		fac=new BigInteger[123];
		fac[1]=BigInteger.ONE;
		BigInteger two=new BigInteger("2");
		for(int i=2;i<=64;i++){
			fac[i]=fac[i-1].multiply(two).add(BigInteger.ONE);
		
		}
		BigInteger pow3[]=new BigInteger[123];
		pow3[1]=BigInteger.ONE;
		BigInteger three=new BigInteger("3");
		for(int i=2;i<=64;i++){
			pow3[i]=pow3[i-1].multiply(three);
		}
		al=new ArrayList<>();
		Scanner sca=new Scanner(System.in);
		while(sca.hasNext()){
			
			BigInteger n=sca.nextBigInteger();
			if(n.compareTo(BigInteger.ZERO)==0)break;
			if(n.compareTo(BigInteger.ONE)==0){
				System.out.println("{ }");
				continue;
			}
			al.clear();
			n=n.subtract(BigInteger.ONE);
			
			DFS(n);
			
			System.out.print("{");
			for(int i=al.size()-1;i>=0;i--){
				System.out.print(" "+pow3[al.get(i)]);
				if(i!=0)System.out.print(",");
				else System.out.print(" ");
			}
			System.out.println("}");
		}
	}

}