My Java Iterative Solution with Explaination

  • 0

    I select each number by iteration. In other to store 1 to n numbers, I create a ArrayList for removing convenience.

    Taking n=3 for example, the first number has three choices 1,2,3, so we can divide the six sequences into three different parts based on the first number. 6/3 = 2 =factorial(n-1). That's why I calculate (k-1)/factorial to determine which parts kth sequence belong.

    After we get the first number, we need to update n, k and remove the selected number from ArrayList, then go to select the next number.

    public class Solution {
    	public String getPermutation(int n, int k) {
    		List<Integer> L = new ArrayList<Integer>();
    		for(int i=1; i<=n; i++){
    		return helper(n, k, L);
    	public String helper(int n, int k, List<Integer> L){
    		String res = "";
    			int factorial = 1;
    			for(int i=1; i<=n-1; i++){
    				factorial *= i;
    			int t = L.get((k-1)/factorial);
    			res += Integer.toString(t);
    			k = (k-factorial*((k-1)/factorial));
    		return res;		

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.