组合总和 - 编程题 - java - 计算机学科 | D & PersonalBlog = D の Java = 别怕路长梦远

# 组合总和

题目要求：

给定一个无重复元素的正整数数组 candidates 和一个正整数

target ，找出 candidates 中所有可以使数字和为目标数 target 的唯

一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字

数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

1 示例 1：

2 输入: candidates = [2,3,6,7], target = 7

3 输出: [[7],[2,2,3]]

	@SuppressWarnings("all")
	public class Demo01
	{
	public static void main(String[] args)
	{
	int arr[] = {2, 3, 6, 7};
	int target = 7;
	List<List<Integer>> dan = dan(arr, target);
	System.out.println(dan);
	}

	public static List<List<Integer>> dan(int candidates[], int target)
	{
	// 创建多列表集合
	List<List<List<Integer>>> dp = new ArrayList<>();
	for (int i = 0; i <= target; i++)
	{
	dp.add(new ArrayList<>()); // 初始化集合
	if (i == 0)
	{
	dp.get(i).add(new ArrayList<>()); // 初始化集合中的集合
	continue;
	}
	for (int candidate : candidates)
	{
	// 避免去用比目标值大的数去进行计算，减少了计算量，减少了浪费的机会
	if (candidate > i)
	{
	continue;
	}
	// 找出所有可以使数字和为目标值的唯一组合
	// 遍历 dp 列表中对应 i - candidata 的所有组合。每个组合都是一个整数列表
	for (List<Integer> list : dp.get(i - candidate))
	{
	// 判断组合是否为空或者组合中最后一个数字是否大于当前候选数并且确保唯一性
	if (!list.isEmpty() && list.get(list.size() - 1) > candidate)
	{
	continue;
	}
	// 创建一个 temp 集合将 list 的所有列表传入该集合中
	List<Integer> temp = new ArrayList<>(list);
	// 将候选数添加到 temp 集合中
	temp.add(candidate);
	// 再将 temp 集合列表添加到 dp 的 i 列表中
	dp.get(i).add(temp);
	}
	}
	}
	// 返回 target 位置的列表数据
	return dp.get(target);
	}
	}

思路分析：