Combination Sum II 组合数求和之2-Leetcode

原题:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,  A solution set is:  [1, 7] [1, 2, 5] [2, 6] [1, 1, 6]


本题和Combination Sum 非常类似,也是从一组数中找到其和为指定值的所有组合。但是本题的特殊之处在于每个给出的候选数只能用一次,且组合不能重复。

思路:

  • 大体思路不变,仍是一个类似深搜的树,只不过原本树的每个节点下的子节点包括自身,而本题的树的每一个节点的子节点是所有排在该节点之后的数,而不包括其本身。如【1,1,2,5,6,7,10】,第一个1的子节点是(1,2,5,6,7,10),第二个1的子节点是(2,5,6,7,10)。
  • 第二个难点在于组合不能重复。譬如仅使用第一个1的组合可以是(1,7),(1,2,5);而仅使用第二个1的组合也可以是(1,7),(1,2,5)。所以要加入一个判断机制。每当循环走过一个节点,我们要判断下一个节点是不是和上一个节点相同,相同的话就必须跳过。

代码如下:

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates, 0, target, new LinkedList<Integer>());
        return ans;
    }
    private List<List<Integer>> ans=new LinkedList<>();
    private  void solve(int[] candidates,int start,int target,LinkedList<Integer> current){
        if (target==0){
            ans.add(copy(current));
            return;
        }
        if (start>=candidates.length){
            return;
        }
        if (target<candidates[start]){
            return;
        }
        else {
            for (int iterator=start;iterator<candidates.length;iterator++){
                if (candidates[iterator]>target){
                    break;
                }
                //如果该节点和上一个节点值相同,那么它的所有组合必然包括在上一个节点的所有组合里,必须跳过
                if (iterator>start&&candidates[iterator]==candidates[iterator-1]){
                    continue;
                }
                current.add(candidates[iterator]);
                solve(candidates, iterator+1, target - candidates[iterator], current); //每使用过iterator,就要+1,使得每个数只用一次
                current.pollLast();
            }
            return;
        }
    }
    private LinkedList<Integer> copy(LinkedList<Integer> source){
        LinkedList<Integer> dest=new LinkedList<>();
        for (int i:source){
            dest.add(i);
        }
        return dest;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

LinkedList源码解析(JDK1.8)

1 package java.util; 2 3 import java.util.function.Consumer; 4 ...

36180
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

240100
来自专栏desperate633

HashSet实现原理分析(Java源码剖析)add(E e)remove(Object o)iterator()小结

本文将深入讨论HashSet实现原理的源码细节。在分析源码之前,首先我们需要对HashSet有一个基本的理解。

28430
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

10430
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

16630
来自专栏desperate633

LintCode 子集题目代码

8530
来自专栏java一日一条

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

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

12520
来自专栏LeetCode

LeetCode 46 & 47. Permutations I&II

Given a collection of distinct integers, return all possible permutations.

29600
来自专栏C语言及其他语言

【编程经验】关于链表、还有编译器

关注我们 最近有小白来问VC6.0和其他编译器怎么下,小编回了一些,但是也是确实比较多......所以今天就不单单分享知识了,还要分享资源! ...

303100
来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

19290

扫码关注云+社区

领取腾讯云代金券