LeetCode——组合

NO.77 组合中等

思路一：回溯法 看到”组合”就不自觉的想到了回溯。

因为是找不重复的组合，只要不重复使用之前更小的元素进行组合即可。

直接套用基本的回溯模板。

List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
    if (n==0||k==0)return res;
    dfs(n,k,new LinkedList<Integer>(),1);
    return res;
}

private void dfs(int n, int k, LinkedList<Integer> track,int index) {
    if (track.size() == k) {
        res.add(new ArrayList<>(track));
        return;
    }
    for (int i = index; i <= n; i++) {
        track.add(i);
        dfs(n,k,track,i+1);
        track.removeLast();
    }
}

时间复杂度：O(k(n!/(n-k)!\k!)) k是生成一个组合的时间，共有n!/(n-k)!*k!种组合。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.77 组合 中等

NO.77 组合中等