文档章节

组合求和 Combination Sum

叶枫啦啦
 叶枫啦啦
发布于 2017/09/04 10:57
字数 391
阅读 9
收藏 0

问题:

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]
]

解决:

① 结果要求返回所有符合要求解的题十有八九都是要利用到递归,而且解题的思路都大同小异,需要另写一个递归函数。注意是可以连续选择同一个数加入组合的。与方法②一样

class Solution { //17 ms
    public static List<List<Integer>> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(candidates,0,target,cur,res);
        return res;
    }
    private static void dfs(int[] candidates, int i, int target, List<Integer> cur, List<List<Integer>> res) {//i表示当前遍历到的下标。
        if(target < 0)    return;
        if(target == 0){
           
res.add(new ArrayList<>(cur));
            return;
        }

        for(int j = i; j < candidates.length && target >= candidates[j]; j ++){
            cur.add(candidates[j]);
            dfs(candidates,j,target - candidates[j],cur,res);//递归向后查找
            cur.remove(cur.size() - 1);//还原链表
        }
    }
}

② 简化

class Solution { //19ms
    List<List<Integer>> res = new ArrayList<>();  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> cur = new ArrayList<>();
        dfs(candidates, 0, target, cur);
        return res;
    } 
    private void dfs(int[] nums, int i,int target, List<Integer> cur) {//i表示当前遍历到的位置
        if (target == 0) {
            res.add(new ArrayList<>(cur));
            // return;
        }    
        for (int j = i; j < nums.length; j ++) {
            if (nums[j] <= target) {
                cur.add(nums[j]);
                dfs(nums, j, target - nums[j], cur);
                cur.remove(cur.size() - 1);
            }
        }
    } 
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
组合求和(元素不能重复使用)Combination Sum II

问题: 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......

叶枫啦啦
2017/09/04
9
0
LeetCode 分类刷题—— Backtracking

Backtracking 的 Tips: 排列问题 Permutations。第 46 题,第 47 题。第 60 题,第 526 题,第 996 题。 组合问题 Combination。第 39 题,第 40 题,第 77 题,第 216 题。 排列和组合杂交问...

一缕殇流化隐半边冰霜
07/06
0
0
列出1~N中k个数其和为给定值 Combination Sum III

问题: Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numb......

叶枫啦啦
2017/11/18
4
0
leetcode permutation/combination

Next Permutation 将整个排列看成是一个数,按该数大小,从小到大排列,求当前排列的下一个排列 // ①从右到左找到第一个非递增的位置 pivot// ②从右到左找到第一个大于 *pivot 的位置 chan...

matrixz
2014/09/07
41
0
Leetcode 39. Combination Sum

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 Version 2 Version 3 Reference https://leetcode.com/problems/combination-sum/description/......

SnailTyan
2018/10/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Android面试常客之Handler全解

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/fnhfire_7030/article/details/79518819 前言:又到了一年...

shzwork
9分钟前
0
0
position sticky 定位

本文转载于:专业的前端网站➫position sticky 定位 1、兼容性 https://caniuse.com/#search=sticky chrome、ios和firefox兼容性良好。 2、使用场景 sticky:粘性。粘性布局。 在屏幕范围内时...

前端老手
15分钟前
1
0
CentOS 7 yum 安装 PHP7.3 教程

参考:https://www.mf8.biz/centos-rhel-install-php7-3/ 1、首先安装 EPEL 源: yum install epel-release 安装 REMI 源: yum install http://rpms.remirepo.net/enterprise/remi-release......

dragon_tech
30分钟前
1
0
Linux物理网卡聚合及桥接

Linux内部实现的bridge可以把一台机器上的多张网卡桥接起来,从而把自己作为一台交换机。同时,LInux bridge还支持虚拟端口,即桥接的不一定都是物理网卡接口,还可以是虚拟接口。目前主要表...

xiangyunyan
31分钟前
1
0
一起来学Java8(一)——函数式编程

在这篇文章中,我们将了解到在Java8下如何进行函数式编程。 函数式编程 所谓的函数式编程就是把函数名字当做值进行传递,然后接收方拿到这个函数名进行调用。 首先来看下JavaScript如何进行函...

猿敲月下码
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部