# Java Recursive and Iterative

• Iterative:

``````    public String getPermutation(int n, int k) {

// e.g n = 5
// [1][1][2][6][24]
int[] factorial = new int[n];
factorial[0] = 1;

for(int i = 1; i < n; i++) {
factorial[i] = factorial[i-1] * i;
}

ArrayList<Integer> numbers = new ArrayList<>();
for(int i = 1; i <= n; i++) {
}

String res = "";
for(int i = n-1; i >= 0; i--) {

int num = (k-1)/factorial[i];
res += numbers.get(num);
k -= num * factorial[i];
numbers.remove(num);
}

return res;
}
``````

Recursive:

``````    public String getPermutation(int n, int k) {

// recursive
// how do you make the problem smaller?
List<Integer> list = new ArrayList<>();
// 1,1,2,6
int[] factorials = new int[n];
factorials[0] = 1;
for(int i = 1; i < n; i++) {
factorials[i] = factorials[i-1] * i;
}

for(int i = 1; i <= n; i++) {
}

return helper(list, k, factorials);
}

private String helper(List<Integer> list, int k, int[] factorials) {

if(list.size() == 0) {
return "";
}

int num = (k-1)/factorials[list.size()-1];
String str = "" + list.get(num);
k -= num * factorials[list.size()-1];
list.remove(num);

return str+helper(list, k, factorials);
}
``````

• 太强了！！！！！！茅塞顿开！！！！！无敌！！！！

• hey, I think if you use recursive solution, you don't need to use factorials array.

``````public class Solution {

List<Integer> list = new ArrayList<Integer>();
StringBuilder result = new StringBuilder();

public String getPermutation(int n, int k) {

for(int i = 0; i < n; i++) {
}

int total = 1;
for(int i = 2; i <= n-1; i++) {
total *= i;
}

return get(n-1, total, k);

}

private String get(int n, int interval, int k){

if(list.size() == 1) {
result.append(list.get(0));
return result.toString();
}
int index = ((k-1) / interval) % list.size();
result.append(list.get(index));
list.remove(index);

return get(n-1, interval/n, k);

}
}
``````

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