锐客网

  1. 首页 > it技术 > >

Combination|Combination Sum 组合数之和

Combination Sum I 题目要求：给定一个数组（元素无重复），和一个目标值，找到所有组合，加起来等于目标值。数组中的元素可以重复使用.
因为我们可以组合任意多个数，然后确认其和是否为目标数，并且返回所有可能的组合，所以必须遍历所有可能性才能求解。
如果遍历所有的可能，这必然会导致效率的问题，所以避免重复搜索，我们搜索的时候只搜索当前或之后的数，不搜索之前的元素。
这是非常典型的DFS并且返回路径的题目，我们采用DFS的方法，在搜索之前我们首先进行排序，因为数组有可能是乱序的。

public class combinationSum { public List> combinationSum(int[] candidates, int target) { List> result=new LinkedList<>(); //返回的列表 List temp=new LinkedList<>(); //临时列表 //首先进行排序，避免重复搜索 Arrays.sort(candidates); //排序 combin(candidates,target,0,temp,result); //返回列表 return result; } private void combin(int[] arrays,int target,int index,List temp,List> 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

Combination Sum II 题目要求：给定一个数组（元素可以有重复），和一个目标值，找到所有组合，加起来等于目标值。数组中的元素不能重复使用。
这个题目与1的区别就是同一个数只能选取一次，而且结果也不能重复。所以我们进行递归的时候在下标加1，这样下一次搜索的时候就避免了重复搜索自己的情况。
并且要防止重复搜索相同的元素，所以要本轮搜索跳过相同的元素。这里我们依然采用DFS的方法，并且先进行排序，理由同上。
public class combinationSum2 { public List> combinationSum2(int[] candidates, int target) { List> result=new LinkedList<>(); List temp=new LinkedList<>(); Arrays.sort(candidates); combin(candidates,target,0,temp,result); return lists; } private void combin(int[] array,int target,int index,List temp,List> result){ if (target<0){ return; }else if (target==0){ list.add(new LinkedList<>(temp)); }else { for (int i=index; iindex &&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 【Combination|Combination Sum 组合数之和】题目要求：给定K和N，从1--9中这几个9个数字组合出来K个数，其和为N。1-9不能重复使用.
这一题是上一题的简化版，与之不同的是这里没有数组，并且要返回在1~9之内满足目标和的列表个数，同一个元素只能选择一次。所以进行搜索的时候可以跳过重复元素的部分，由于要求列表的长度要等于k，所以我们还要对于k进行控制。
这里依然采用DFS的方法。
public class Solution { public List> combinationSum3(int k, int n) { List> result=new LinkedList<>(); //返回的列表 Listtemp=new LinkedList<>(); //临时列表 combin(k,n,1,temp,result); return result; } private void combin(int k,int target,int index,List temp,List> 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

这一题参考了下面的连接。
参考：https://segmentfault.com/a/1190000008607396
上述代码已放在我的GitHub中：https://github.com/heiqi1/LeetCode

    推荐阅读


    上一篇：实在写不下去，花五分钟读读它

    下一篇：晨间日记|晨间日记 从减重聊开去-1