本文共 4022 字，大约阅读时间需要 13 分钟。
原题链接：
Given a set of candidate numbers (C) (without duplicates) 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. 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] ]这个题目的意思是给定一个集合，集合中的元素不重复，并且包含一个目标值（即目标值也是集合中的一个元素），从集合中找出所有不重复的元素的组合，使得这些元素之和等于目标值。注意，结果集合中的元素可以重复出现。
例如：给定集合 [2, 3, 6, 7] 和目标值7，符合上述题目要求的结果集合为： [ [7], [2, 2, 3] ]问题分析：可以采用DFS搜索算法求解。
算法设计
package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.Arrays;import java.util.Iterator;import java.util.List;public class CombinationSum { /* * 可能的答案存在多个集合的情况，所以combinationSum方法返回值为一个List， * 而list中的每一个元素均为一个List集合，其中每一个元素的类型均为Integer * * 输入参数：目标数组和目标值 * * * */ public List > combinationSum(int[] candidates, int target) { List > ans = new ArrayList<>(); //对目标数组排序 Arrays.sort(candidates); /* * 调动dfs算法 * 输入参数的含义：ans为答案List集合 * new ArrayList () 为存放临时结果的ArrayList集合 * candidates为候选值 * target为目标值 * 0 为开始搜索的位置下标 * */ dfs(ans, new ArrayList (), candidates, target, 0); return ans; } /* * dfs算法设计 * * */ private void dfs(List > ans, List list, int[] cand, int remain, int from) { //如果没有剩余的元素了，则结束搜索，返回。（搜索结束条件） if (remain < 0) { return; } //如果搜索到最后将临时结果加入答案中，并返回。结束搜索 if (remain == 0) { ans.add(new ArrayList (list)); return; } //从开始位置（from参数），到cand数组的最后一个元素位置，进行搜索 for (int i = from; i < cand.length; ++i) { // cand[] sorted; from is the starting point of picking elements at this level list.add(cand[i]); //remain-cand[i]的含义是当目标值减去候选数组的元素之后，对剩余的数组元素再进行搜索 dfs(ans, list, cand, remain - cand[i], i); list.remove(list.size() - 1); } } public static void main(String args[]) { int[] array= { 2, 3, 6, 7}; int target=7; CombinationSum cs=new CombinationSum(); List > list=cs.combinationSum(array, target); Iterator > itx=list.iterator(); while(itx.hasNext()) { List lt=itx.next(); System.out.println(lt); } }}
运行结果：
[2, 2, 3]
[7]另外一种求解方法
递归思想求解 首先把=target的数保存到list,将package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Iterator;import java.util.List;public class CombinationSum2 { public List > combinationSum(int[] array, int target) { List > list = new ArrayList >(); Arrays.sort(array);//数组排序 //各种特殊情况 if(array.length == 0 || array[0] > target) return list; int len = 0; boolean isAdd = false;//控制与target相等的数只添加一次 for(int i = 0; i< array.length;i++){ if(array[i] == target){ if(!isAdd){ //如果未添加 List al = new ArrayList (); al.add(target); list.add(al); isAdd = true;//标记已添加 } }else if(array[i] < target){ //只要比target小的值，大的值肯定不满足，排除 array[len++] = array[i];//新数组 } } //只存在array[0] < target 或 array[0] > target if(array[0] > target)//肯定已没有符合要求的组合 return list; //array[0] < target for(int i = 0; i < len; i++){ //循环搜索符合要求的数字组合 int[] b = Arrays.copyOfRange(array, i, len);//不含>=t数据的新数组 if(array[i] > target)//如果array[i]，肯定以后的数据已不符合，返回 break; //相等于已经有了一个值array[0]了 List > newList = new ArrayList >(); //递归求解 newList = combinationSum(b,target-array[i]); if(newList.size() > 0){ //里面有符合要求的数据 for(int j = 0; j < newList.size();j++){ newList.get(j).add(array[i]);//新返回的各个值添加array[0] Collections.sort(newList.get(j));//排序 list.add(newList.get(j));//最终添加 } } } return list; } public static void main(String args[]) { int[] array = { 2, 3, 6, 7 }; int target = 7; CombinationSum2 cs = new CombinationSum2(); List > list = cs.combinationSum(array, target); Iterator > itx = list.iterator(); while (itx.hasNext()) { List lt = itx.next(); System.out.println(lt); } }}
（完）
转载地址：http://gwtdi.baihongyu.com/