【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 提供了集合框架来解决此类问题,线性表、链表、哈希表等...

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

【Java提高十六】集合List接口详解

在编写java程序中,我们最常用的除了八种基本数据类型,String对象外还有一个集合类,在我们的的程序中到处充斥着集合类的身影!java中集合大家族的成员实在...

2513
来自专栏云霄雨霁

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

1060
来自专栏desperate633

LintCode 子数组之和题目分析代码

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

622
来自专栏互扯程序

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

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

4956
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

2186
来自专栏恰同学骚年

剑指Offer面试题:12.在O(1)时间删除链表结点

  在单向链表中删除一个结点,最常规的做法无疑是从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点。这种思路由于需要顺序查找,时间复杂度自然就是...

691
来自专栏Jack的Android之旅

疯狂java笔记之线性表

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

1052
来自专栏移动端开发

Java集合类总结

前言: 这篇准备好好总结一下Java的集合类,在顺便带上Arrays,把这几者之间的关系说清楚,在java.util包中提供了一些集合类,这些集合类又被称作容...

2759
来自专栏小勇DW3

ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题

平时我们使用ArrayList比较多,但是我们是否知道ArrayList在进行foreach的时候不能直接通过list的add或者move方法进行删除呢,

1783

扫码关注云+社区