LeetCode刷题：39. Combination Sum
原题链接：https://leetcode.com/problems/combination-sum/description/
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<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>();//对目标数组排序Arrays.sort(candidates);/** 调动dfs算法* 输入参数的含义：ans为答案List集合* new ArrayList<Integer>() 为存放临时结果的ArrayList集合* candidates为候选值* target为目标值* 0 为开始搜索的位置下标* */dfs(ans, new ArrayList<Integer>(), candidates, target, 0);return ans;}/** dfs算法设计* * */private void dfs(List<List<Integer>> ans, List<Integer> list, int[] cand, int remain, int from) {//如果没有剩余的元素了，则结束搜索，返回。（搜索结束条件）if (remain < 0) {return;}//如果搜索到最后将临时结果加入答案中，并返回。结束搜索if (remain == 0) {ans.add(new ArrayList<Integer>(list));return;}//从开始位置（from参数），到cand数组的最后一个元素位置，进行搜索for (int i = from; i < cand.length; ++i) { // cand[] sorted; from is the starting point of picking elements at this levellist.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<Integer>> list=cs.combinationSum(array, target);Iterator<List<Integer>> itx=list.iterator();while(itx.hasNext()) {List<Integer> 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<List<Integer>> combinationSum(int[] array, int target) { List<List<Integer>> list = new ArrayList<List<Integer>>(); 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<Integer> al = new ArrayList<Integer>(); 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<List<Integer>> newList = new ArrayList<List<Integer>>(); //递归求解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<Integer>> list = cs.combinationSum(array, target);Iterator<List<Integer>> itx = list.iterator();while (itx.hasNext()) {List<Integer> lt = itx.next();System.out.println(lt);}}
}
（完）