leetcode39-Combination Sum

2024-05-04 18:12
文章标签 sum combination leetcode39

本文主要是介绍leetcode39-Combination Sum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

分析

类似这种题目的套路一定是遍历数组+递归的解法,我们可以记录每次递归遍历到的下标,因为可以重复使用元素所以每次递归的时候需要考虑当前遍历到的元素,每次递归都用target-当前元素,递归结束的条件就是target=0的时候,但是如果target<0说明一系列元素累加起来不符合预期也可以结束递归

import java.util.List;
import java.util.ArrayList;public class combinationSum {private static List<Integer> cur = new ArrayList();private static List<List<Integer>> res = new ArrayList();public static void main(String[] args) {int[] arr = {2,3,6,7};getRes(arr,7,0);for(List<Integer> lis : res) {for(Integer num:lis) {System.out.print(num + " ");}System.out.println();}}public static void getRes(int[] arr,int target,int start) {if(target < 0) {return;}if(target == 0) {res.add(new ArrayList(cur));return;}for(int i = start;i<arr.length;i++) {cur.add(arr[i]);getRes(arr,target-arr[i],i);cur.remove(cur.size()-1);}}
}

这篇关于leetcode39-Combination Sum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959805

相关文章

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t

如何导入sun.misc.BASE64Encoder和sum.misc.BASE64Decoder

右击项目名--->Build Path--->Configure Build Path...--->java Build Path--->Access rules:1 rule defined,added to all librar...   --->Edit --->Add...

18. 4 Sum

题目: 解答: 与之前的三数之和的解法类似,也是先排序,然后不断剔除不可能的条件,最后两个参数,通过两头求和计算得出。 代码: class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int len = nums.size

apt-get update更新源时,出现“Hash Sum mismatch”问题

转载自:apt-get update更新源时,出现“Hash Sum mismatch”问题 当使用apt-get update更新源时,出现下面“Hash Sum mismatch”的报错,具体如下: root@localhost:~# apt-get update ...... ...... W: Failed to fetch http://us.archive.ubuntu.com/ub

[LeetCode] 303. Range Sum Query - Immutable

题:https://leetcode.com/problems/range-sum-query-immutable/description/ 题目 Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example: Given nums

[LeetCode] 64. Minimum Path Sum

题:https://leetcode.com/problems/minimum-path-sum/description/ 题目 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers

[LeetCode] 404. Sum of Left Leaves

题:https://leetcode.com/problems/sum-of-left-leaves/description/ 题目 Find the sum of all left leaves in a given binary tree. Example: 3/ \9 20/ \15 7There are two left leaves in the binary t

数论 --- 费马小定理 + 快速幂 HDU 4704 Sum

Sum  Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=4704   Mean:  给定一个大整数N,求1到N中每个数的因式分解个数的总和。   analyse: N可达10^100000,只能用数学方法来做。 首先想到的是找规律。通过枚举小数据来找规律,发现其实answer=pow(2,n-1);

LeetCode - 40. Combination Sum II

40. Combination Sum II  Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个待选集合s和一个数n,选出所有相加之和为n的组合.(每个元素只能选一次) analyse: 递归求解. 在递归进入

LeetCode - 39. Combination Sum

39. Combination Sum  Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个待选集合s和一个数n,让你找出集合s中相加之和为n的所有组合.(每个数可选多次) analyse: 作此题需对递归有一定的