题目内容

给定一个整数数组 candidates，其中所有整数互不相同，另外给定一个目标整数 target。需要从 candidates 中挑选若干数字，使得这些数字的和恰好等于 target。选择过程中，同一个候选数字可以被重复使用任意多次。

对于两个组合，只要存在某个数字在两个组合中被选中的次数不同，就认为它们是不同的组合。请找出所有满足要求的组合，输出顺序不受限制。

约束条件：

• candidates 的长度在 1 到 30 之间。
• candidates 中的每个整数都在 2 到 40 之间。
• candidates 中的所有整数互不相同。
• target 的取值范围为 1 到 40。
• 有效组合的数量少于 150。

输入描述

输入包含两个参数：

• candidates：一个整数数组，表示可供选择的候选数字。数组中的元素互不相同。
• target：一个整数，表示目标和。

每个候选数字可以被重复选择任意次。

输出描述

返回一个二维整数数组，表示所有元素之和等于 target 的组合。

• 二维数组中的每个一维数组表示一种组合。
• 同一组合中，候选数字可以重复出现。
• 如果两个组合中任意数字的选取次数不同，则认为它们是不同的组合。
• 返回结果的顺序不作要求。
• 如果不存在满足条件的组合，则返回空数组 []。

样例1

输入

3 6
2 3 4

输出

3 3
2 4
2 2 2

说明

候选数字为 2、3、4，目标是 6。

可以用 $3+3=6$ 得到组合 $[3,3]$，用 $2+4=6$ 得到组合 $[2,4]$，用 $2+2+2=6$ 得到组合 $[2,2,2]$。这三个组合都满足要求，输出顺序不限。

样例2

输入

1 2
2

输出

2

说明

候选数字只有 2，目标值是 2。

选择一次 2 即可得到 $2=2$，所以唯一组合是 $[2]$。

样例3

输入

2 3
2 4

输出

说明

候选数字为 2 和 4，目标值是 3。

如果选择 2，还差 1，但候选数字中没有 1，也不能再选 2，因为 $2+2=4>3$；如果选择 4，则直接超过目标值 3。因此没有有效组合，返回空数组。