Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input:n = 4, k = 2Output:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
这里有个比较细节但是能提升性能的地方,在代码中用(1)标出
一般会想到的条件是i<=n
以n=5,k=3为例
如果条件是i<=n,则回溯树长这样:
i <= n - k + 1的时候则是:
假如k很接近n,如果用i<=n就会浪费很多次遍历。比如n=k=5,
i<=n+k-1的话,只需遍历一次。i<=n则遍历很多次,已经不是一个数量级耗时了
class Solution {
List<List<Integer>> res = new LinkedList<>();
ArrayList<Integer> cur = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
doCombine(n, k, 1);
return res;
}
private void doCombine(int n, int k, int start) {
if (0 == k) {
res.add(new ArrayList<>(cur));
return;
}
for (int i = start; i <= n - k + 1; i++) { // ---------------- (1)
cur.add(i);
doCombine(n, k - 1, i + 1);
cur.remove(cur.size() - 1);
}
}
}
最后,有没有大佬能把准确的时间复杂度公式算出来?还请不吝赐教~
网友评论