資訊專欄INFORMATION COLUMN
摘要：和唯一的不同是組合中不能存在重復(fù)的元素，因此，在遞歸時(shí)將初始位即可。
Combination Sum I Problem
Given a set of candidate numbers (C) 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.
NoticeAll numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
基本思路與Combinations一致，遞歸模板詳見：https://segmentfault.com/a/11...
有兩個(gè)點(diǎn)需要注意：在組合中的數(shù)必須是升序排列，所以在調(diào)用dfs函數(shù)之前要先排序；另外，由于組合里允許有重復(fù)數(shù)，dfs調(diào)用自身時(shí)，初始位start(=i)的位置不變，依然從i開始，只需將target減小num[i]即可。
public class Solution {
List> res = new ArrayList<>();
public List> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
helper(candidates, 0, target, new ArrayList());
return res;
}
public void helper(int[] c, int start, int t, List pre) {
if (t < 0) return;
if (t == 0) res.add(pre);
for (int i = start; i < c.length; i++) {
List cur = new ArrayList(pre);
cur.add(c[i]);
helper(c, i, t-c[i], cur);
}
}
}
Combination Sum II
Problem
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 used once in the combination.
NoticeAll numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
Given candidate set [10,1,6,7,2,1,5] and target 8,
A solution set is:
[
[1,7],
[1,2,5],
[2,6],
[1,1,6]
]
和Combination Sum I唯一的不同是組合中不能存在重復(fù)的元素，因此，在dfs遞歸時(shí)將初始位+1即可。
Solutionpublic class Solution {
List> res = new ArrayList>();
public List> combinationSum2(int[] num, int target) {
Arrays.sort(num);
helper(num, 0, target, new ArrayList());
return res;
}
public void helper(int[] num, int start, int target, List pre) {
if (target < 0) return;
if (target == 0) {
res.add(pre);
return;
}
for (int i = start; i < num.length; i++) {
if (i > start && num[i] == num[i-1]) continue;
List cur = new ArrayList (pre);
cur.add(num[i]);
helper(num, i+1, target-num[i], cur);
}
}
}
Combination Sum III & IV link: here
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65721.html
Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...
摘要：整個(gè)過程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...
摘要：建立動(dòng)規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對(duì)所有點(diǎn)作為終點(diǎn)的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時(shí)的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
摘要：和完全一樣的做法，只要在初始化首行和首列遇到時(shí)置零且即可。對(duì)了，數(shù)組其它元素遇到也要置零喏，不過就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...
Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...
閱讀 2704·2023-04-25 19:13
閱讀 4048·2021-09-22 15:34
閱讀 3062·2019-08-30 14:23
閱讀 1470·2019-08-29 17:17
閱讀 1616·2019-08-29 16:05
閱讀 1547·2019-08-29 13:26
閱讀 1224·2019-08-29 13:19
閱讀 563·2019-08-29 13:16
