【LEETCODE】模拟面试-39. Combination Sum

和subset区别:规定了子集的sum==target

注意,这里传递的起始位置是i,而不是position+1,but why???

helper(res, path, candidate, sum - candidate[i], i);  

code区别: notice:需要sort if条件里 sum >= candidate[i]

Arrays.sort(candidate);    //需要sort

helper(res, path, candidate, sum, 0);     //参数多了sum

//每次path加入新元素后,sum减去元素:sum - candidate[i]

if ( sum == 0 )      //stop条件是sum被减为0了

for ( int i = position; i < candidate.length && sum >= candidate[i]; i++ )
//sum余额不足覆盖下一个i的话,就不用再走了,这就是sort的好处

图:新生大学

https://leetcode.com/problems/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] ]

input: a candidate set, eg, [1, 2, 3, 6, 7], a target sum integer, eg, 4 output: find all possible unique combinations which can sum to be the target, and in each combination, the numbers can be repeated at unlimited times. eg, [2, 2] -> 4

We need a list of list to store result, and a list called path to store current single path. There is also a position to locate the starting point for every path.

Notice the sum target is able to decrease itself during the process.

For convenience, we will sort the candidate array first.

The starting position will iterate from 0 to candidate.length - 1

Since this question allows repeated numbers, for each path, we can do this repeated work by passing the same starting point i to next level, rather than i + 1.

So that, for each unique number, the path will firstly add it for unlimited times until return. Then remove this number one by one, to leave space for next number. Moreover, the next number will also repeatedly add itself first until return.

And every time if current sum is larger than current number, we can add the number to current path, and pass the remaining sum = current sum - current number to next level.

Until current sum is zero, we will add the path to final result list.

After each path has finished its trip and returns to upper level, we should remove the last number of current path, to accept other new numbers.

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidate, int sum){        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //corner
        
        //core
        List<Integer> path = new ArrayList<>();
        
        Arrays.sort(candidate);
        
        helper(res, path, candidate, sum, 0);       //start from position = 0
        
        return res;
    }
    
    public void helper(List<List<Integer>> res, List<Integer> path, int[] candidate, int sum, int position){
        //base
        if ( sum == 0 ){                                    
            res.add(new ArrayList<Integer>(path));
            return ;                                        
        }
        
        //current
        for ( int i = position; i < candidate.length && sum >= candidate[i]; i++ ){ 
            path.add(candidate[i]);
            //next: pass down remaining 'sum', and afterwards 'start position'
            helper(res, path, candidate, sum - candidate[i], i);        
            path.remove(path.size() - 1);
        }
        
        return ;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

集合类操作优化经验总结

在实际的项目开发中会有很多的对象,如何高效、方便地管理对象,成为影响程序性能与可维护性的重要环节。Java 提供了集合框架来解决此类问题,线性表、链表、哈希表等...

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

LeetCode-49-Group-Anagrams

输入一个字符串数组,输出的是:将相同字符的字符串放在一个数组的二维数组。相同字符的处理,基本就是要对字符串排序的。然后需要考虑的就是排序好的那一个字符串怎么存的...

8110
来自专栏wannshan(javaer,RPC)

JDK PriorityBlockingQueue remove(Object o) 源码分析

先知道PriorityBlockingQueue 是利用数组存储二叉堆实现。最小值(最优先)放在queue[0]位置。 //删除某个元素 public bool...

38070
来自专栏Ryan Miao

在java中使用redis

在java中使用redis很简单,只需要添加jedist.jar,通过它的api就可以了。而且,api和redis的语法几乎完全相同。以下简单的测试: 参考:h...

66680
来自专栏Jack的Android之旅

疯狂java笔记之线性表

从数据的逻辑结构来分,数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来,应用程序中的数据大致哟如下四种基本的逻辑结构。

11620
来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

52860
来自专栏Android开发小工

Java集合解惑

本文取自工匠若水的qq群里的Java基础题目,把里面有关Java集合放在一起。 全文github地址

14920
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

46060
来自专栏用户画像

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。

10330
来自专栏云霄雨霁

字符串查找----R向单词查找树

13100

扫码关注云+社区

领取腾讯云代金券