LintCode 数字组合 II题目代码

题目

给出一组候选数字(C)和目标数字(T),找出C中所有的组合,使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

注意事项

所有的数字(包括目标数字)均为正整数。 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。 解集不能包含重复的组合。

样例 给出一个例子,候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8 ,

解集为:[[1,7],[1,2,5],[2,6],[1,1,6]]

代码

public class Solution {
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    public List<List<Integer>> combinationSum2(int[] candidates,
            int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }

        Arrays.sort(candidates);
        List<Integer> combination = new ArrayList<Integer>();
        helper(candidates, 0, combination, target, results);

        return results;
    }

    private void helper(int[] candidates,
                        int startIndex,
                        List<Integer> combination,
                        int target,
                        List<List<Integer>> results) {
        if (target == 0) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (i != startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (target < candidates[i]) {
                break;
            }
            combination.add(candidates[i]);
            helper(candidates, i + 1, combination, target - candidates[i], results);
            combination.remove(combination.size() - 1);
        }
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

7366
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

790
来自专栏武培轩的专栏

剑指Offer-链表中倒数第k个结点

题目描述 输入一个链表,输出该链表中倒数第k个结点。 思路 为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针: 快指针从链表的头指针开始遍历向前走k-...

3499
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3315
来自专栏小二的折腾日记

牛客网-剑指offer-2

二叉树是觉得很烦的东西了,比链表复杂很多,看着头都有点疼啊,但是没办法,生活就是这样,只有把不会的会了才会进步,怕的变得不怕才能越来越厉害。 常规的理解一下:二...

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

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

2886
来自专栏小樱的经验随笔

从零开始学建树(树的分治,树的重心)

分治算法在树的路径问题中的应用 一、树的分治算法 树的分治算法是分治思想在树型结构上的体现。 任一个具有n个节点的连通路,它的任何一棵树的树枝数为n-1 分治:...

2674
来自专栏郭耀华‘s Blog

剑指offer第二天

18.二叉树的镜像 操作给定的二叉树,将其变换为源二叉树的镜像。 ? /** public class TreeNode { int val = 0...

2876
来自专栏算法channel

深度优先搜索和回溯结合后的终极模板

昨天 这5道算法题 都可以套用这个模板 推送了一个深度搜索和回溯结合的题目和另4道类似题,今天,逐个分析后4道题,最后提炼出模板。

1370
来自专栏拭心的安卓进阶之路

Java 集合深入理解(16):HashMap 主要特点和关键方法源码解读

前面我们介绍了 哈希相关概念:哈希 哈希函数 冲突解决 哈希表,这篇文章我们来根据 JDK 1.8 源码,深入了解下使用频率很高的 HashMap 。 读完本...

2835

扫码关注云+社区

领取腾讯云代金券