【微软2014实习生及秋令营技术类职位在线测试】题目2 : K-th string

3
2 2 2
2 2 7
4 7 47

0101
Impossible
01010111011

import java.lang.String;
import java.lang.StringBuilder;
import java.net.Inet4Address;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Permutation {
	static int sum ;
	
	public static void main(String[] args)
	{
		int T ;
		Scanner jin = new Scanner(System.in);
		T = jin.nextInt();
		while(T-- > 0)
		{
			int N, M, K;
			StringBuilder stringBuilder = new StringBuilder();
			N = jin.nextInt();M = jin.nextInt();K = jin.nextInt();
			
			if (!((M+N) >= 2 && (N+M) <= 33)) {
				System.out.println("Impossible");
				continue;
			}
			
			if(N < 0 || M < 0)
			{
				System.out.println("Impossible");
				continue;
			}
			
			for (int i = 0; i < N; i++) {
				stringBuilder.append(‘0‘);
			}
			for (int i = 0; i < M; i++) {
				stringBuilder.append(‘1‘);
			}
			sum = 0;
			permutation(stringBuilder.toString().toCharArray(), 0, stringBuilder.length()-1, K);
			if (sum < K) {
				System.out.println("Impossible");
			}
		}
	}
	public static void permutation(char[] str, int start, int end, int K) {
		if (start == end) {
			sum++;
			//System.out.print(sum);
			//System.out.print("	");
			//System.out.print(new String(str));
			//System.out.print("	");
			if (sum == K) {
				System.out.println(new String(str));
				return ;
			}
			
		}
		else {
			for (int i = start; i <= end; i++) {
				if(!Isduplicated(str, start, i))
				{
					char tmp = str[start];
					str[start] = str[i];
					str[i] = tmp;
					
					permutation(str, start+1, end, K);

					tmp = str[start];
					str[start] = str[i];
					str[i] = tmp;
				}
				
			}
		}
		
	}
	public static boolean Isduplicated(char[] ch, int start, int end) {
		for (int i = start; i < end; i++) {
			if (ch[i] == ch[end]) {
				return true;
			}
		}
		return false;
	}
	
}