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

相关文章

来自专栏iOSer成长记录

RunLoop 源码阅读

1755
来自专栏软件开发 -- 分享 互助 成长

享元模式

一、简介 1、享元模式运用共享技术有效地支持大量细粒度的对象。 2、享元模式是为了减少同种类的实例化,以达到节省内存的目的。 3、类成员函数 抽象享元类(Fly...

1789
来自专栏HT

基于HTML5 Canvas 实现地铁站监控

伴随国内经济的高速发展,人们对安全的要求越来越高。为了防止下列情况的发生,您需要考虑安装安防系统: 提供证据与线索:很多工厂银行发生偷盗或者事故相关机关可以根据...

1945
来自专栏Android点滴积累

Android Activity返回键控制的两种方式

Android Activity返回键监听的两种方式 1、覆写Activity的OnBackPressed方法 官方解释: Called when the a...

2117
来自专栏xx_Cc的学习总结专栏

iOS-RunLoop充满灵性的死循环

3798
来自专栏积累沉淀

js监控输入密码检测大写键盘是否锁定

? <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <meta http-equiv="...

1765
来自专栏GIS讲堂

Openlayers2唯一值渲染

702
来自专栏哈雷彗星撞地球

RunLoop总结:RunLoop基础知识

没有实际应用场景,很难理解一些抽象空洞的东西,所以前面几篇文章先介绍了RunLoop的几个使用场景。 另外AsyncDisplayKit中也有大量使用RunL...

1072
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - RunLoop

4737
来自专栏编程坑太多

程序猿真的觉得写代码比女朋友重要吗?

693

扫码关注云+社区