LeetCode_83_CombinationSumII


1. question: 组合总和II(中等)

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/combination-sum-ii

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1
2
3
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

2. answers

这道题要注意以下几点:

  1. 数组中存在重复的数字。
  2. 一个组合中:一个数字(下标)只能出现一次。(如果有重复的数字,那么该数字最多能出现重复次数
  3. 不同组合中:即使数组中有重复的数字,也只能出现一次。

如案例1所示,虽然1出现了两次,但是对于组合[1, 7],却只能有一个。也就是说,如果数组中有重复的数组,那么一个组合内的数字重复是允许的,但是无论什么情况,组合之间是不能重复的。

因此,

  1. 当求解一个组合的所有数字时,按照正常的步骤做就行,每次递归,其取值区间从当前元素的下一个元素开始。
  2. 当求解不同的组合时,如果当前元素的选择和上一次相同,那么就不进行本次遍历,进行下一次选择,直到元素不同。

其实第2点有一个难点,因为递归,始终在同一个函数中,那么如何确定是本元素的不同次选择,还是一个组合中的不同元素选择呢?如果回溯了,就说明是本元素的不同次选择。因此,上述第2点的判断应该放到回溯后面。代码如下所示:

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
63
64
65
66
67
68
69
70
71
72
73
public class Solution_0082 {

public List<List<Integer>> result = new ArrayList<>();
public LinkedList<Integer> group = new LinkedList<>();

public void recur(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];

// 递归下一个元素,注意,下一个元素的下标取值,保证了集合内元素不会重复使用(不是数值)
recur(candidates, target, i + 1);

// 回溯
target += candidates[i];
group.removeLast();

// 保证了本次选择的元素和上一次不会重复,从而避免组合之间的重复。(数值)
// 因为递归的缘故,所以必须此处要保证判断的是:同一个元素的不同选择,而不是一个组合中的不同元素选择。
// 但是为了保证上面的条件,所以只能放在递归结束之后,即将要进行本元素的下一次选择。如果二者一样,则手动跳过下一次。
// 直到下一次选择不是相同的元素
// 注意,本循环只能判断到倒数第二个元素,当倒数第一个和倒数第二个元素相同时,i会自加到倒数第一个元素。
// 但是因为外层还有for循环,也会自加,所以就会跳出循环,仍然满足总体要求。
while(i< candidates.length - 1 && candidates[i] == candidates[i+1]) {
i++;
}
}
}

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

Arrays.sort(candidates);

recur(candidates, target, 0);

return result;
}

public static void main(String[] args) {
System.out.println();

int[] candidates = {10, 1, 2, 7, 6, 1, 5};
int target = 8;

// int[] candidates = {2, 5, 2, 1, 2};
// int target = 5;

// int[] candidates = {2, 2, 2};
// int target = 2;

Solution_0082 s = new Solution_0082();
List<List<Integer>> result = s.combinationSum2(candidates, target);

for(List<Integer> list: result) {

for(Integer i: list)
System.out.print(i + "\t");

System.out.println();
}
}
}

到此,组合似乎有这么几种题型:

  1. 给定一个不重复的集合,求解任意k个数的组合。
  2. 给定一个不重复的集合,求解任意k个数总和为n的组合。
  3. 给定一个不重复的集合,求解任意总和为n的组合。
  4. 给定一个可重复的集合,求解任意总和为n的组合。

其实似乎根据上面的情形,还可以有:

  1. 给定一个可重复的集合,求解任意k个数总和为n的组合。

其实主要把握两点即可:

  1. 组合中不同位置元素的选择。(递归)
  2. 组合中同一位置元素的选择。(循环)

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录