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.
Note:
- 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.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is: [7] [2, 2, 3]
思路：需要回溯的思想。对数组里面的每个数，用递归的方式叠加，每次递归将和sum与target作比较，若相等则加入结果list，sum>target则舍弃，并返回false，若sum<target，则继续进行递归。第一种sum=target的情况下，在加入结果list后，要将当前一种结果最后加入的元素remove，并继续对后面的元素进行递归；在第二种sum>target的情况下，则需要将当前结果的最后加入的两个元素remove，并继续对后面的元素进行递归。第三种情况sum<target，无需删除直接递归。
注意元素可以重复，所以下一次递归是从当前递归元素开始。
public class S039 {
//backtracking--回溯算法
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
Arrays.sort(candidates);//很关键的一步
findConbination(result,temp,0,0,target,candidates);
return result;
}
public boolean findConbination(List<List<Integer>> result,List<Integer> temp,int sum,int level,int target,int[] candidates){
if(sum == target){
result.add(new ArrayList<>(temp)); //从内存复制，防止后面的改变对其发生影响
return true;
}else if(sum>target){
return false;
}else{
for(int i = level;i<candidates.length;i++){//思考level参数的作用
temp.add(candidates[i]);
// sum += candidates[i];思考这一行注释掉并把sum的增加加在下一行参数里面的原因
if(!findConbination(result,temp,sum+candidates[i],i,target,candidates)){//i表示下一次递归从当前递归的位置开始
i = candidates.length;
}
temp.remove(temp.size()-1);
}
return true;
}
}
}
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.
Note:
- 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.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is: [1, 7] [1, 2, 5] [2, 6] [1, 1, 6]
思路：与前一题的不同之处在于结果要求同一位置的元素只能出现一次，但是值相同在数组中位置不同的元素可以同时出现。与前一题的不同就是下一次递归都是从当前递归的下一个元素开始。另外测试集不相同，前一题的测试集中不会出现同一数组中有相同的元素，所以不用额外去重。这一题同一数组会出现相同元素，所以得在元素向前移的时候跳过相同的元素来进行去重。
public class S040 {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> rets = new ArrayList<List<Integer>>();
List<Integer> ret = new ArrayList<Integer>();
find(candidates,0,0,target,rets,ret);
return rets;
}
public static boolean find(int[] candidates,int sum,int level,int target,List<List<Integer>> rets,List<Integer> ret){
if(sum == target){
rets.add(new ArrayList<>(ret));
return true;
}else if(sum > target){
return false;
}else{
for(int i = level;i<candidates.length;i++){
ret.add(candidates[i]);
if(!find(candidates,sum+candidates[i],i+1,target,rets,ret)){//i+1表明下一次递归从当前递归的下一位元素开始
i = candidates.length;
}
//去重
while(i<candidates.length-1&&ret.get(ret.size()-1) == candidates[i+1]){
i++;
}
ret.remove(ret.size()-1);
}
return true;
}
}
}
Combination Sum III
Find 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:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
思路：这一题还是参照了前两题，相当于把前两题中的candidates数组变为nums={1,2,3,4,5,6,7,8,9},然后再在每一次比较结果时加上结果list大小的比较，当前list的大小不超过k。
也不用额外去重。
public class S216 {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
if(n<k*(k+1)/2||n>45||k>9||k<1){
return result;
}
int[] nums = {1,2,3,4,5,6,7,8,9};
find(nums,k,n,0,0,result,temp);
return result;
}
public static boolean find(int[] nums,int k, int n, int sum,int level,
List<List<Integer>> result,List<Integer> temp){
if(temp.size()>k||sum>n){
return false;
}else if(sum == n&&temp.size() == k){
result.add(new ArrayList<>(temp));
return true;
}else{
for(int i = level;i<nums.length;i++){
temp.add(nums[i]);
if(!find(nums,k,n,sum+nums[i],i+1,result,temp)){
i = nums.length;
}
temp.remove(temp.size()-1);
}
return true;
}
}
}