Combination Sum I
题目要求：给定一个数组（元素无重复），和一个目标值，找到所有组合，加起来等于目标值。数组中的元素可以重复使用.
因为我们可以组合任意多个数，然后确认其和是否为目标数，并且返回所有可能的组合，所以必须遍历所有可能性才能求解。
如果遍历所有的可能，这必然会导致效率的问题，所以避免重复搜索，我们搜索的时候只搜索当前或之后的数，不搜索之前的元素。
这是非常典型的DFS并且返回路径的题目，我们采用DFS的方法，在搜索之前我们首先进行排序，因为数组有可能是乱序的。
public class combinationSum {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result=new LinkedList<>();//返回的列表
List<Integer> temp=new LinkedList<>();//临时列表
//首先进行排序，避免重复搜索
Arrays.sort(candidates);//排序
combin(candidates,target,0,temp,result);
//返回列表
return result;
}
private void combin(int[] arrays,int target,int index,List<Integer> temp,List<List<Integer>> result){
//如果目标和的差值小于0，表示该路径出现错误
if (target<0){
return;
//等于表示，这是一条正确的路径，将其add到result上
}else if (target==0){
//这里每次重新创建temp列表，避免与之前的列表重复
result.add(new LinkedList<>(temp));
//否则的话，目标和的差值大于0，继续进行深度优先搜索
}else {
//选取之后的每个数字都是一种可能性，其中index的作用是避免搜索之前搜索过的数组元素
for (int i=index;i<arrays.length;i++){
temp.add(arrays[i]);
//先加入元素，然后进行搜索，这里进行DFS搜索，如果不满足，就把temp列表里的元素去除掉
combin(arrays,target-arrays[i],i,temp,lists);
//目标和不符合，所以将临时列表的最新值去除，然后尝试下一个元素
temp.remove(temp.size()-1);
}
}
}
}
Combination Sum II
题目要求：给定一个数组（元素可以有重复），和一个目标值，找到所有组合，加起来等于目标值。数组中的元素不能重复使用。
这个题目与1的区别就是同一个数只能选取一次，而且结果也不能重复。所以我们进行递归的时候在下标加1，这样下一次搜索的时候就避免了重复搜索自己的情况。
并且要防止重复搜索相同的元素，所以要本轮搜索跳过相同的元素。这里我们依然采用DFS的方法，并且先进行排序，理由同上。
public class combinationSum2 {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result=new LinkedList<>();
List<Integer> temp=new LinkedList<>();
Arrays.sort(candidates);
combin(candidates,target,0,temp,result);
return lists;
}
private void combin(int[] array,int target,int index,List<Integer> temp,List<List<Integer>> result){
if (target<0){
return;
}else if (target==0){
list.add(new LinkedList<>(temp));
}else {
for (int i=index;i<array.length;i++){
// 跳过本轮剩余的重复元素
if(i>index &&array[i]==array[i-1]) continue;
temp.add(array[i]);
// 递归时下标加1
combin(array,target-array[i],i+1,temp,result);
temp.remove(temp.size()-1);
}
}
}
}
Combination Sum III
题目要求：给定K和N，从1--9中这几个9个数字组合出来K个数，其和为N。1-9不能重复使用.
这一题是上一题的简化版，与之不同的是这里没有数组，并且要返回在1~9之内满足目标和的列表个数，同一个元素只能选择一次。所以进行搜索的时候可以跳过重复元素的部分，由于要求列表的长度要等于k，所以我们还要对于k进行控制。
这里依然采用DFS的方法。
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result=new LinkedList<>(); //返回的列表
List<Integer>temp=new LinkedList<>();//临时列表
combin(k,n,1,temp,result);
return result;
}
private void combin(int k,int target,int index,List<Integer> temp,List<List<Integer>> result){
//这里对于k进行控制，若是列表长度大于k仍然没有符合要求，直接返回
if(target<0||temp.size()>k){
return;
//这里加上一个控制条件
}else if(target==0&&temp.size()==k){
result.add(new LinkedList<>(temp));
return;
}else{
//这里不使用数组元素，只用使用1~9即可
for(int i=index;i<=9;i++){
temp.add(i);
//这里i+1是指跳过自己
combin(k,target-i,i+1,temp,result);
temp.remove(temp.size()-1);
}
}
}
}
Combination Sum IV
题目要求：给定一个正整数数组（元素无重复），给定目标target，找出组合的个数，使得组合中元素的和等于target。数组元素可以重复使用.
一开始尝试使用DFS的思路来解题，没想到时间超时，于是发现这一题是动态规划的题目。
我们首先建立一个一维数组dp，长度为target+1，dp[i]存储的是目标i时所得到的组合数。
从dp[1]开始计算到dp[target]，每次计算dp[i]时的方法是，从头开始遍历nums数组。
如果i>=nums[j],dp[i]=dp[i]+dp[i-nums[j]]
（比如题目中的例子[1，2，3]
计算dp[1] ：
从头开始遍历nums
当j =0时 因为1 >= nums[0] 故 dp[1] = dp[1]+dp[1- nums[0]],即
dp[1] = dp[1]+dp[0] = 1;
当j=1 时 因为1 < nums[1] 故 不再运算 故dp[1] = 1;
计算 dp[2]:
当j =0时 因为2 >= nums[0] 故 dp[2] = dp[2]+dp[2- nums[0]],即
dp[2] = dp[2]+dp[1] = 1;
当j =1时 因为2 >= nums[1] 故 dp[2] = dp[2]+dp[2- nums[1]],即
dp[2] = dp[2]+dp[0] = 2;
当j=2 时 因为2 < nums[2] 故 不再运算 故dp[2] = 2;
public class Solution {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] dp=new int[target+1];
for(int i=1;i<dp.length;i++){
for(int num:nums){
if (num == i) dp[i]++;
else if (num < i) dp[i] += dp[i-num];
else break;
}
}
return dp[target];
}
}
这一题参考了下面的连接。
上述代码已放在我的GitHub中：https://github.com/heiqi1/LeetCode
