1. question: 组合总和（中等）
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum
示例 1：
1
2
3
4
5
6
| 输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
|
示例 2：
1
2
| 输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
|
示例 3：
1
2
| 输入: candidates = [2], target = 1
输出: []
|
提示：
1
2
3
4
| 1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都 互不相同
1 <= target <= 500
|
2. answers
这道题猛地一看，还是比较灵活的。首先是给定了数组和target，求解数组中和为target的组合。
- 对组合的元素是否重复无要求
- 对组合的元素个数无要求
- 要求结果中的组合不重复，即至少有一个数字的频率不一样
思路总体上和组合一样，不过，这里将数组进行升序排列，方便后续剪枝；另外，将target每次减去组合中的元素值，不设置元素和变量sums。最开始想的时候，因为允许元素重复使用，所以我在做的时候没有限制每个组合的元素的下标取值范围。因此这肯定会出现重复结果的。代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| public class Solution_0081 {
public List<List<Integer>> result = new ArrayList<>();
public LinkedList<Integer> group = new LinkedList<>();
public void recurCom(int[] candidates, int target) {
if(target == 0) {
result.add(new ArrayList<>(group));
return;
}
for (int i = 0; i < candidates.length; i++) {
if(target < candidates[i]) return;
group.add(candidates[i]);
target -= candidates[i];
recurCom(candidates, target);
group.removeLast();
target += candidates[i];
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
recurCom(candidates, target);
return result;
}
public static void main(String[] args) {
System.out.println();
int[] candidates = {2, 3, 5};
Solution_0081 s = new Solution_0081();
List<List<Integer>> result = s.combinationSum(candidates, 8);
for(List<Integer> list: result) {
for(Integer i: list)
System.out.print(i + "\t");
System.out.println();
}
}
}
|
但是，因为一个组合中允许元素重复使用。所以，只是在一层循环中，不限制元素的使用。但是在不同的组合中，是限制下标的，这样才不会出现重复组合。
以[2, 3, 5, 6]为例，target=8。
- 第一个集合，取2，后续的元素，可以在下标[0, 3]之间任意。即元素可重复。
- 但是当第二个集合的时候，第一个元素为3，后续的元素，只能是下标[1, 3]之间任意取。因为包含2且包含3的情况，已经在第一个集合中取遍了。
- 所以，不同集合之间的下标还是有限制的。
代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| public class Solution_0081_02 {
public List<List<Integer>> result = new ArrayList<>();
public LinkedList<Integer> group = new LinkedList<>();
public void recurCom(int[] candidates, int target, int startIndex) {
if(target == 0) {
result.add(new ArrayList<>(group));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if(target < candidates[i]) return;
group.add(candidates[i]);
target -= candidates[i];
recurCom(candidates, target, i);
group.removeLast();
target += candidates[i];
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
recurCom(candidates, target, 0);
return result;
}
public static void main(String[] args) {
System.out.println();
int[] candidates = {2, 3, 6, 7};
Solution_0081_02 s = new Solution_0081_02();
List<List<Integer>> result = s.combinationSum(candidates, 7);
for(List<Integer> list: result) {
for(Integer i: list)
System.out.print(i + "\t");
System.out.println();
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
