这是问题：https://leetcode.com/problems/combinations/
这是我的解决方案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);
}
}
}
结果：小规模测试用例已通过。但大规模测试用例超时。
提交结果：时间限制已超出 上一次执行的输入：10，5
解决方案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);
}
}
}
所有测试用例均已通过。
主要区别在于列表的克隆。 但为什么？ 方案A是错误的还是只是慢？ 为什么在这里使用克隆更快？ 真的很困惑。