Jan 19 - Permutation Sequence; BackTracking; Factorial;

public class Solution {
    public static String getPermutation(int n, int k) {
        String result = "";
        if(n == 1) return result + 1;
        int factorial_n = factorial(n-1);
        boolean[] isUsed = new boolean[n];
        return addDigit(factorial_n, k-1, n-1, isUsed);
    }
    
    public static int factorial(int n){
        if(n == 1 || n == 0) return 1;
        return n*factorial(n-1);
    }
    
    public static String addDigit(int factorial, int k, int n, boolean[] isUsed){
    	int times = k/factorial;
        int remain = k%factorial;
            int i = 0;
            int count = 0;
            for(; i < isUsed.length; i++){
                if(!isUsed[i]) count++;
                if(count == times+1) break;
                    
            }
            isUsed[i] = true;
            if(n == 0) return String.valueOf(i+1);
            if(n == 1){
            	String s = i+1+addDigit(1, remain, n-1, isUsed);
            	System.out.println("n == 1: "+ (i+1));
            	return s;
            }
            String s = i+1+addDigit(factorial/n, remain, n-1, isUsed);
            return s;
    }
}