This is the question:https://leetcode.com/problems/combinations/
This is my solution 1:
public class Solution {
public List<List<Integer>> combine(int n, int k){
List<List<Integer>> result = new ArrayList<List<Integer>>();
combine(n, k, 1, result, new ArrayList<Integer>());
return result;
}
public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
if(k == 0){
result.add(l);
return;
}
for(int i = start; i <= n; ++i){
l.add(i);
combine(n, k - 1, i + 1, result, l);
}
}
}
Result: small test cases passed. But big test cases time exceed.
Submission Result: Time Limit Exceeded Last executed input: 10, 5
Solution 2:
public class Solution {
public List<List<Integer>> combine(int n, int k){
List<List<Integer>> result = new ArrayList<List<Integer>>();
combine(n, k, 1, result, new ArrayList<Integer>());
return result;
}
public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
if(k == 0){
result.add(l);
return;
}
for(int i = start; i <= n; ++i){
ArrayList<Integer> a = (ArrayList<Integer>) l.clone();
a.add(i);
combine(n, k - 1, i + 1, result, a);
}
}
}
Passed all test cases.
the main difference is clone of the list. But why? is the solution A wrong or just slow? Why using clone is faster here? Really confused.
The first solution is indeed incorrect. Try invoking combine(5,3), and sending it to System.out, and you'll see the output for the first is:
[[1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5]]
You'll notice that it's the same list in each index position - you really do need to create a new array each time. For the second, correct solution, the output is:
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
This means that the first solution is slower because you're adding numbers to a larger and larger list each time. For higher values of n and k, that list can be very large, and copying the backing array of ArrayList when it needs to expand becomes a very expensive operation - much more expensive than copying/creating a number of small lists.