spring自定义注解

77. 组合

难度中等416收藏分享切换为英文接收动态反馈

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

通过次数109,730

提交次数144,781

题解

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new LinkedList<>();
        if( k <=0 || n < k) return res;
        traceBack(n, k, 1, new LinkedList<Integer>(), res);
        return res;

    }

    void traceBack(int n , int k,int start, LinkedList<Integer> temp, List<List<Integer>> res){
        if( temp.size() == k){
            res.add(new LinkedList<>(temp));
            return;
        }
        for(int i =start; i <= n; i++){
            temp.add(i);
            traceBack(n, k,i+1, temp, res );
            temp.pollLast();
        }
    }
}

如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 11 个数；
如果组合里有 2 ，那么需要在 [3, 4] 里再找 11数。注意：这里不能再考虑 11，因为包含 11 的组合，在第 1 种情况中已经包含。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考

[回溯算法 + 剪枝（Java）](回溯算法 + 剪枝（Java）)

注意遍历的i 应该从 start开始， 并且每次递归都是 i+1 ， 如果直接 temp.contains(i) 进行判空的话，还是会重复

优化

针对搜索

// 从当前搜索起点 begin 遍历到 n
for (int i = begin; i <= n; i++) {
    path.addLast(i);
    dfs(n, k, i + 1, path, res);
    path.removeLast();
}

事实上，如果 n = 7, k = 4，从 55 开始搜索就已经没有意义了，这是因为：即使把 55 选上，后面的数只有 66 和 77，一共就 33 个候选数，凑不出 44 个数的组合。因此，搜索起点有上界，这个上界是多少，可以举几个例子分析。

容易知道：搜索起点和当前还需要选几个数有关，而当前还需要选几个数与已经选了几个数有关，即与 path 的长度相关。我们举几个例子分析：

例如：n = 6 ，k = 4。

path.size() == 1 的时候，接下来要选择 33 个数，搜索起点最大是 44，最后一个被选的组合是 [4, 5, 6]；
path.size() == 2 的时候，接下来要选择 22 个数，搜索起点最大是 55，最后一个被选的组合是 [5, 6]；
path.size() == 3 的时候，接下来要选择 11 个数，搜索起点最大是 66，最后一个被选的组合是 [6]；

再如：n = 15 ，k = 4。
path.size() == 1 的时候，接下来要选择 33 个数，搜索起点最大是 1313，最后一个被选的是 [13, 14, 15]；
path.size() == 2 的时候，接下来要选择 22 个数，搜索起点最大是 1414，最后一个被选的是 [14, 15]；
path.size() == 3 的时候，接下来要选择 11 个数，搜索起点最大是 1515，最后一个被选的是 [15]；

可以归纳出：

搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
其中，接下来要选择的元素个数 = k - path.size()，整理得到：

搜索起点的上界 = n - (k - path.size()) + 1
所以，我们的剪枝过程就是：把 i <= n 改成 i <= n - (k - path.size()) + 1 ：

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com