[LeetCode] 39. Combination Sum ☆☆☆(数组相加等于指定的数)
2023-09-14 09:07:35 时间
https://leetcode.wang/leetCode-39-Combination-Sum.html
描述
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解析
回溯法
参考这里) ,就是先向前列举所有情况,得到一个解或者走不通的时候就回溯。和37题有异曲同工之处,也算是回溯法很典型的应用,直接看代码吧。
动态规划
看原文
代码
回溯法
public List<List<Integer>> combinationSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); backtrack(list, new ArrayList<>(), nums, target, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i); //找到了一个解或者 remain < 0 了,将当前数字移除,然后继续尝试 tempList.remove(tempList.size() - 1); } } }
相关文章
- Java实现LeetCode 5449. 检查数组对是否可以被 k 整除 (更改题意)
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 565 数组嵌套(没有重复值的数组)
- Java实现 LeetCode 491递增子序列
- Java实现 LeetCode 445 两数相加 II
- Java实现 LeetCode 404 左叶子之和
- Java实现 LeetCode 290 单词规律
- Java实现 LeetCode 223 矩形面积
- Java实现 LeetCode 174 地下城游戏
- Java实现 LeetCode 108 将有序数组转换为二叉搜索树
- Java实现LeetCode_0007_ReverseInteger
- 【哈希表】LeetCode 560. 和为K的子数组【中等】
- LeetCode-713. 乘积小于 K 的子数组【滑动窗口】
- leetcode 99. 恢复二叉搜索树
- 【LeetCode Python实现】300. 最长递增子序列(中等)动态规划
- 【LeetCode Python实现】737. 句子相似性 II(中等)
- Leetcode 1991. 找到数组的中间位置(暴力枚举)
- Leetcode 345. 反转字符串中的元音字母
- [LeetCode] 238. 除自身以外数组的乘积 ☆☆☆(左积*右积)
- leetcode-1 Two Sum 找到数组中两数字和为指定和
- 【Leetcode刷题Python】852. 山脉数组的峰顶索引
- 【Leetcode刷题Python】生词本单词整理
- 【Leetcode刷题Python】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 【LeetCode】337. 打家劫舍 III