Combination Sum |
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.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is: [7] [2, 2, 3]
Notice
- All 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]
分析：递归
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> listsAll = new ArrayList<>();
Arrays.sort(candidates);
helper(, , candidates, target, new ArrayList<>(), listsAll);
return listsAll;
}
public static void helper(int index, int total, int[] candidates, int target, List<Integer> list, List<List<Integer>> listsAll) {
if (index >= candidates.length || total >= target) return;
list.add(candidates[index]);
total += candidates[index];
if (total == target) {
listsAll.add(new ArrayList<>(list));
}
helper(index, total, candidates, target, list, listsAll);
total = total - candidates[index];
list.remove(list.size() - );
helper(index + , total, candidates, target, list, listsAll);
}
}
Combination Sum II
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.
Notice
- All 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]
]
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> listsAll = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
helper(, , candidates, target, new ArrayList<>(), listsAll);
return listsAll;
}
public static void helper(int index, int total, int[] candidates, int target, List<Integer> list, List<List<Integer>> listsAll) {
if (index >= candidates.length || total >= target) return;
list.add(candidates[index]);
total += candidates[index];
if (total == target) {
listsAll.add(new ArrayList<Integer>(list));
}
helper(index + , total, candidates, target, list, listsAll);
total = total - candidates[index];
list.remove(list.size() - );
while (index + < candidates.length && candidates[index] == candidates[index + ]) {
index++;
}
helper(index + , total, candidates, target, list, listsAll);
}
}
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.
分析： 这题和change coin非常相似。
public class Solution {
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == ) return ;
int[] dp = new int[target + ];
dp[] = ;
for (int i = ; i <= target; i++) {
for (int num : nums) {
if (i - num >= ) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
参考请注明出处：cnblogs.com/beiyeqingteng/