資訊專欄INFORMATION COLUMN
摘要：此時(shí)，若也正好減小為，說明當(dāng)前集合是正解，加入數(shù)組。兩個(gè)無法得到正解的情況是在為，而不為時(shí)，當(dāng)然已經(jīng)無法得到正解，。在不為而卻已經(jīng)小于等于的情況下，此時(shí)仍要加入其它數(shù)以令為，而要加入的數(shù)都是到的正整數(shù)，所以已無法滿足令為的條件，。
Combination Sum I & II: link
Combination Sum III ProblemFind all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:[[1,2,4]]Example 2:
[[1,2,6], [1,3,5], [2,3,4]]Note
思路和Combination Sum II一樣，用DFS遞歸求解。
加一個(gè)參數(shù)count = k，count每當(dāng)有新的數(shù)i加入計(jì)算集合cur則減一；同時(shí)，target，也就是給定的n，也要減少i。
當(dāng)count為0時(shí)，集合里就有k個(gè)數(shù)了。此時(shí)，若target也正好減小為0，說明當(dāng)前集合pre是正解，pre加入res數(shù)組。
兩個(gè)無法得到正解的情況是：
在count為0，而target不為0時(shí)，當(dāng)然已經(jīng)無法得到正解，return。
在count不為0而target卻已經(jīng)小于等于0的情況下，此時(shí)仍要加入其它數(shù)以令count為0，而要加入的數(shù)都是1到9的正整數(shù)，所以已無法滿足令target為0的條件，return。
public class Solution {
List> res = new ArrayList<>();
public List> combinationSum3(int k, int n) {
helper(1, k, n, new ArrayList());
return res;
}
public void helper(int start, int count, int target, List pre) {
if (count == 0) {
if (target == 0) res.add(pre);
else return;
}
else {
if (target <= 0) return;
if (target > 0) {
for (int i = start; i <= 9; i++) {
List cur = new ArrayList (pre);
cur.add(i);
helper(i+1, count-1, target-i, cur);
}
}
}
}
}
Combination Sum IV
Problem:
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
Follow up:What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
DP method
public class Solution {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] dp = new int[target+1];
for (int i = 1; i <= target; i++) {
for (int num: nums) {
if (num == i) dp[i]++;
else if (num < i) dp[i] += dp[i-num];
else break;
}
}
return dp[target];
}
}
Optimized DP
public class Solution {
public int backPackVI(int[] nums, int target) {
int[] dp = new int[target+1];
Arrays.sort(nums);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num: nums) {
if (num <= i) dp[i] += dp[i-num];
}
}
return dp[target];
}
}
Another DP
public class Solution {
public int backPackVI(int[] nums, int target) {
int[] dp = new int[target+1];
Arrays.fill(dp, -1);
Arrays.sort(nums);
return helper(nums, dp, target);
}
int helper(int[] nums, int[] dp, int target){
if (dp[target] >= 0) return dp[target];
dp[target] = 0;
for (int i = 0; i < nums.length; i++){
if (target > nums[i]) dp[target] += helper(nums, dp, target-nums[i]);
else if (target == nums[i]) {
dp[target]++;
break;
}
}
return dp[target];
}
}
DFS: Exceeded time limit
public class Solution {
int count = 0;
public int backPackVI(int[] nums, int target) {
//int count = 0;
int sum = 0;
dfs(nums, target, sum);
return count;
}
void dfs(int[] nums, int target, int sum){
if (sum > target) return;
else if (sum == target) {
count++;
}
for (int i = 0; i < nums.length; i++) {
dfs(nums, target, sum+nums[i]);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66029.html
摘要：題目要求輸入和，找到所有個(gè)不同數(shù)字的組合，這些組合中數(shù)字的和為參考，解答這是一道典型的的題目，通過遞歸的方式記錄嘗試的節(jié)點(diǎn)，如果成功則加入結(jié)果集，如果失敗則返回上一個(gè)嘗試的節(jié)點(diǎn)進(jìn)行下一種嘗試。 題目要求 Find all possible combinations of k numbers that add up to a number n, given that only numbe...
摘要：和唯一的不同是組合中不能存在重復(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...
摘要：深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸?？臻g思路因?yàn)槲覀兛梢匀我饨M合任意多個(gè)數(shù)，看其和是否是目標(biāo)數(shù)，而且還要返回所有可能的組合，所以我們必須遍歷所有可能性才能求解。這題是非?；厩业湫偷纳疃葍?yōu)先搜索并返回路徑的題。本質(zhì)上是有限深度優(yōu)先搜索。 Combination Sum I Given a set of candidate numbers (C) and a target number (...
找出string里的單詞。 186. Reverse Words in a String II, 434. Number of Segments in a String combination類型題 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...
摘要：參考思路和非常類似，只是這里需要增加進(jìn)行重復(fù)處理的部分。題目要求題目中新添的要求包括數(shù)組中存在重復(fù)值，而且數(shù)組中每個(gè)值只可以使用一次。需要注意的是，既然數(shù)組中存在重復(fù)的值，就要注意可能會(huì)將重復(fù)的情況加入結(jié)果數(shù)組。 參考 思路和leetcode39 combination sum 非常類似，只是這里需要增加進(jìn)行重復(fù)處理的部分。請(qǐng)參考我對(duì)leetcode39進(jìn)行解答的這篇博客。 題目要求 ...
閱讀 1175·2021-11-16 11:45
閱讀 1042·2021-09-04 16:41
閱讀 3088·2019-08-29 16:40
閱讀 2865·2019-08-29 15:34
閱讀 2681·2019-08-29 13:11
閱讀 1743·2019-08-29 12:58
閱讀 1735·2019-08-28 18:00
閱讀 1785·2019-08-26 18:26
