专栏首页架构之路Combination Sum II 组合数求和之2-Leetcode

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 条评论
登录 后参与评论

相关文章

  • Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

    一、背景介绍 强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足 自反性:顶点V...

    老白
  • Combination Sum 组合数求和-Leetcode

    原题: Given a set of candidate numbers (C) and a target number (T), find all uniqu...

    老白
  • 离线Tarjan算法-最近公共祖先问题

    转载自Tarjan算法 LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通...

    老白
  • 只要 5 分钟,让你立刻拥有自己的小程序 | 知晓云

    Hello,各位知晓程序的读者们,我是犯迷糊的小羊。目前是 ifanr 的一只前端攻城狮,同时也是知晓云团队的一员。

    知晓君
  • 学术资讯|人工智能在医疗领域的应用建议:普惠、精准,打通“最后一公里”

    今年两会上,包括医疗健康在内的民生话题依然是热点。多个医疗相关提案议案涉及人工智能等前沿科技。

    优图实验室
  • 事务,时间戳与混合逻辑时钟

    这篇文章接上文mongodb4.0事务实现浅析。 mongo从3.6之后,开始进行WT-TIMESTAMP-PROJ,后续server层引入了带签名的逻辑时钟l...

    MongoDB中文社区
  • JDBC基础入门(3)

    事务 事务是由一步/几步数据库操作序列组成的逻辑执行单元, 这些操作要么全部执行, 要么全部不执行. 注: MySQL事务功能需要有InnoDB存储引擎的支持,...

    Java帮帮
  • zookeeper-3. java操作z

    1. 创建会话方法:客户端可以通过创建一个zookeeper实例来连接zookeeper服务器。

    py3study
  • Eclipse中把代码误删掉 恢复方法

    如果把本地的程序整个文件以及包名删除了,那么你应该想到以前这个程序的名字,然后先建立起来。

    用户5166556
  • 基础知识 | 每日一面(78)

    读者:我的程序的屏幕提示和中间输出有时显示在屏幕上, 尤其是当我用管道向另一个程序输出的时候。

    C语言入门到精通

扫码关注云+社区

领取腾讯云代金券