# TLE Kidding Me. Obviously fast.

• This causes a TLE in case of (9,8)
After comparing with other accepted kernals in other questions, I ran all for 999 times and found it obviously faster in this case and return right result.
The logic is recursion: first arrange [1,2,3,.... k] when k=n
then the result of combine(n) will cover all result of combine(n-1) and those which replace one digit in all single list in result of combine(n-1).
Not fast in most case but at least in this case (9,8) and works.
Why TLE?

``````public class Solution {

public List<List<Integer>> combine(int n, int k) {
if(k>n)
return Collections.<List<Integer>>emptyList();
List<List<Integer>> ans = new ArrayList<List<Integer>>();

if(n==k){
ArrayList<Integer> newlist = new ArrayList<Integer> ();
for(int i = 1; i<= n; i++){
}
}else{
List<List<Integer>> pre = combine(n-1,k);
for(final List<Integer> oldlist: pre){
for(int j = 0; j<k;j++){
List<Integer> newlist = new ArrayList<Integer> (oldlist);
newlist.set(j,n);
}
}
}
return ans;

}``````

• I don't know Java. But do you think copy the old list every time is efficient?

• I tried the same code but I don't the efficiency of copying old list is low since we eventually construct the same amount of lists. So I guess something wrong with the copying -- elements in lists point to the same Object and cause the evaluation of OJ into infinite loop.

• First of all, when it reported TLE with last input was (9, 8), it does not necessarily mean it is this input is error-prone, but means you got timed out when running this input. And in this case, input (9, 8), perfectly works. The problem is when input n - k > 1, for example, input (3, 1), your program will return [[1],[2],[3],[3]] which contains duplicates. Number of duplicates will get much more when the difference between n and k grows. That's where it cost more time. So unfortunately the algorithm has something fundamentally wrong : ( But, really genius thought!

• Thanks so much! You've pointed out the most valuable point.
After consideration, I know it's wrong about my algorithm and it's also low efficient for general case. When I tried to get input(5,2) and the input(4,2) return something like {4,3;4,2;4,1;} by replacing the second position with '5', we get three same list. I have to remove duplicate and it's quite costly.

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