[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

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

Note:

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

For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:

[
  [7],
  [2, 2, 3]
]

【解释】 给定一个集合(无重复元素),和一个目标值target,要求候选集合中的元素可能的和为target的所有集合。 【思路】 很典型的回溯法

public class Solution {
    public void combinationSumCore(List<List<Integer>> results, List<Integer> result,int[] candidates,int index,int target,int sum){
        if(sum==target) {//得到集合加入results中并返回
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.length;i++){
            result.add(candidates[i]);
            sum+=candidates[i];
            combinationSumCore(results, result,candidates,i,target,sum);//由于这里候选集合的元素可以重复使用,所以从当前元素开始递归,在Combination SumII和III中,是从i+1开始的
            sum-=candidates[i];
            result.remove(result.size()-1);//回溯
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        List<Integer> result=new ArrayList<>();
        combinationSumCore(results,result,candidates,0,target,0);
        return results;
    }

}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

1779
来自专栏coolblog.xyz技术专栏

LinkedList 源码分析(JDK 1.8)

LinkedList 是 Java 集合框架中一个重要的实现,其底层采用的双向链表结构。和 ArrayList 一样,LinkedList 也支持空值和重复值。...

4327
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3093
来自专栏各种机器学习基础算法

PHP SPL(PHP 标准库)

一、什么是spl库? SPL是用于解决典型问题(standard problems)的一组接口与类的集合。 此扩展只能在php 5.0以后使用,从PHP 5...

2746
来自专栏架构之路

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

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

2665
来自专栏Java Web

数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

1071
来自专栏武培轩的专栏

剑指Offer-二叉搜索树的第k个结点

题目描述 给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 /  3 7 / / 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。 思路 利用...

2847
来自专栏JMCui

ArrayList 和 LinkedList的执行效率比较

一、概念:     一般我们都知道ArrayList* 由一个数组后推得到的 List。作为一个常规用途的对象容器使用,用于替换原先的 Vector。允许我们快...

3539
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之反转链表(九度OJ1518)

题目描述: 输入一个链表,反转链表后,输出链表的所有元素。 (hint : 请务必使用链表) 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试...

1989
来自专栏老马说编程

(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在Tre...

1878

扫码关注云+社区