leetCode 77&39. Combinations & Combination Sum

77.Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

题目大意:在1 ... n 中任意选取k个数,将所有的情况罗列出来

思路:这个就是典型的组合问题。同样是采用回溯算法。

解法:

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

public void combineHelper(int n, int k,List<List<Integer>> res,int start,LinkedList<Integer> resTemp){
    if (resTemp.size() == k){
        res.add(new LinkedList<>(resTemp));
        return;
    }
    for(int i=start;i<=n;i++ ){
        resTemp.addLast(i);
        combineHelper(n,k,res,i+1,resTemp);
        resTemp.removeLast();
    }
}

其实,我们可以对上面的算法进行一些优化,试想如果对于1,2,3,4,5,6,7,8这个序列中,查找长度为4的组合(n=8,k=4),我们的start==6时,是否还能找到满足要求的序列呢?明显的不能,因为剩余的数字长度已经小于k了。

所以当 k-resTemp.size >n-i+1时候就不能找到了。所以for循环的执行条件为i <= n - k+ resTemp.size()+1。

于是:

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

public void combineHelper(int n, int k,List<List<Integer>> res,int start,LinkedList<Integer> resTemp){
    if (resTemp.size() == k){
        res.add(new LinkedList<>(resTemp));
        return;
    }
    for(int i=start;i <= n - k+ resTemp.size()+1;i++ ){
        resTemp.addLast(i);
        combineHelper(n,k,res,i+1,resTemp);
        resTemp.removeLast();
    }
}

从leetcode的提交结果上看,从原来的34ms提升到4ms,可见这一个优化是非常有效的。实际上这就是回溯算法常见的剪枝法,把不满足条件的提前排除掉。

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题目大意:在一个没有重复数字的数组中挑选数字,使其和等于target,一个数字可以取多次。

解法一:

思路:这实际上也是一个组合问题。

这个是我一开始的解法:for循环中的if是为了避免重复情况,比如[2,3,3]和[3,2,3],总是从当前的数字或者后面的数字中寻找,而不从前面的数字中寻找。

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        combinationSumHelper(candidates,target,res,new LinkedList<>());
        return res;
    }
    public void combinationSumHelper(int[] candidates, int target,List<List<Integer>> res,LinkedList<Integer> tempRes){
        if (target < 0) return;
        if (0 == target){
            res.add(new ArrayList<>(tempRes));
        }

        for (int i = 0;i<candidates.length;i++){
            if (tempRes.isEmpty()){
                tempRes.addLast(candidates[i]);
            }else {
                if(candidates[i]>=tempRes.getLast()){
                    tempRes.addLast(candidates[i]);
                }else continue;
            }
            combinationSumHelper(candidates,target-candidates[i],res,tempRes);
            tempRes.removeLast();
        }
    }

解法二:

这里的start的使用非常的巧妙。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    combinationSumHelper(candidates,target,res,new ArrayList<>(),0);
    return res;
}

public void combinationSumHelper(int[] candidates, int target,List<List<Integer>> res,ArrayList<Integer> tempRes,int start){
    if (target < 0) return;
    if (0 == target){
         res.add(new ArrayList<>(tempRes));
    }
    for (int i = start;i<candidates.length;i++){
        tempRes.add(candidates[i]);
        //这里的参数i就代替了解法一里面的if判断
        combinationSumHelper(candidates,target-candidates[i],res,tempRes,i);  
        tempRes.remove(tempRes.size()-1);
    }
}

值得注意的是:回溯算法的退出条件。

总结:

组合问题的解法的整体思路与排列问题相似,但是排列问题的for是从0开始查询,而组合问题是从一个变量start开始查询的,因为start之前的已经处理过了,这样就避免重复。有关排列问题的回顾可以参考《LeetCode 46 & 47. Permutations I&II》。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

面试题18(以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是?)

以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是? A)HashMap实现Map接口,它允许任何类型的键和值对象,...

30750
来自专栏数据结构与算法

2879 堆的判断

2879 堆的判断 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用...

32580
来自专栏博岩Java大讲堂

Java集合--List

42770
来自专栏吾爱乐享

java之学习集合带All的方法的案例分析

11730
来自专栏java一日一条

Java 容器&泛型(1):认识容器

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:...

12420
来自专栏小灰灰

JDK容器学习之LinkedHashMap(二):迭代遍历的实现方式

LinkedHashMap 如何保障有序的遍历 前一篇《JDK容器学习之LinkedHashMap (一):底层存储结构分析》 中介绍了LinkedHashM...

37570
来自专栏机器学习入门

LWC 52:687. Longest Univalue Path

LWC 52:687. Longest Univalue Path 传送门:687. Longest Univalue Path Problem: Given...

23970
来自专栏余林丰

Java迭代器Iterator

 之前我们实现了迭代器模式,很多编程语言实际上已经内置了迭代器类,比如Java就为我们实现了迭代器Iterator。我们首先来看Iterator中的源码。 通过...

264100
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

21590
来自专栏芋道源码1024

Jedis 对 Redis 的操作详解

本篇主要阐述Jedis对redis的五大类型的操作:字符串、列表、散列、集合、有序集合。

22130

扫码关注云+社区

领取腾讯云代金券