【数据结构】算法 组合的和 Combination Sum

目录

• 组合的和 Combination Sum
• 思路
• Tag

组合的和 Combination Sum

一个没有重复元素的正整数组candidates 和一个正整数target。从candidates 中找出所有可以满足数字加和为target 的组合，candidates 中的数字可以被重复使用，组合中的数字一样，顺序不一样，也认为是一组相同的解答。

in：candidates = [2,3,6,7], target = 7
out：[[7],[2,2,3]]

思路

看似有规律，但好像有没有规律。最简单也是最笨的方法暴力搜索，使用DFS，穷举出所有的组合，计算出是否满足target，满足就认为是一组答案。

当然穷举的过程中也要优雅，一些明显无法得到解答的组合，不用走完就可以直接丢弃。

也就是说剪枝+回溯，可以解决一些冗余的问题。目标和是target，每次要从candidate中取一个数减掉，然后不断的重复这个过程，类似一个树形结构。如果candidates中有m个数，那这棵树就是个m叉树，每个节点都有m个子节点。如果暴力的走完所有的节点，是会找到答案，但是有一些路明显是不通的，所以我们要在遍历的过程中，寻找可能满足的路径，也就是说不满足特定条件的路径没有继续寻找的必要。

为了保证，不会漏掉和重复，先将candidates进行排序。

从索引0开始，设计方法backtrack，ind代表使用索引为ind的数，target为当前还剩余的数，track代表已经选中的组合数。

dfs的方法结束的标记

1. target==0
2. ind索引遍历完
3. target小于arr[ind]

由于允许一个数可以无限制的使用，backtrack(ind,arr,track,target-arr[ind])，可以在一个数上一直去循环查找可能解。也可以跳过当前的数，去查下一个backtrack(ind+1,arr,track,target)。

通过上面的2个情况来缩小dfs的分支。

 public List<List<Integer>> ans;
 public List<List<Integer>> combinationSum(int[] candidates, int target) { 
	ans = new LinkedList<Integer>();	
	LinkedList<Integer> track = new LinkedList<Integer>();	
	Arrays.sort(candidates);
	backtrack(0,candidates,track,target);
	return ans;	
 }
 
 public void backtrack(int ind,int[] arr,LinkedList<Integer> track ,int target){
	 if(target==0){		 
		 ans.add(new LinkedList(track));
		 return ;
	 }	  
	 if(ind==arr.length){
		 return;
	 }	 
	 if(target - arr[ind]<0){
		 return;
	 }	 
	 backtrack(ind+1,arr,track,target);	 
	 track.add(arr[ind]);	 
	 backtrack(ind,arr,track,target- arr[ind]);
	 track.removeLast();	 
	 return;	 
 }

Tag

DFS backtrack