leetcode40.Combination Sum II

发表于 更新于 分类于 ，

参考

思路和leetcode39 combination sum 非常类似，只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。

思路与代码

这题与leetcode39的思路基本相同，利用递归的方法记录前一次情况作为下一次的初始情况。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。
例如，如果数组为[2,2,2,6],目标值为8，可能会在结果数组中出现多次[2,6]
同样的，在进行递归的子遍历的时候也要注意，可能会出现重复值，例如数组为[2,2,2,6],目标值为10，则结果集[2,2,6]也可能出现多次，所以在子遍历中也要记得去除重复情况。
代码如下

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
public class CombinationSum2_40 {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int length = candidates.length;
        for(int i = 0 ; i<length ; i++){
            //去除外围重复情况
            if(i>0 && candidates[i] == candidates[i-1]){continue;}
            if(candidates[i] == target){
                result.add(Arrays.asList(candidates[i]));
            }else{
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(candidates[i]);
                combinationSum2(candidates, target-candidates[i], i+1, temp);
            }
        }
        return result;
    }
    
    public void combinationSum2(int[] candidates, int target, int startAt, List<Integer> currentList){
        for(int i = startAt ; i<candidates.length ; i++){
            if(candidates[i] == target){
                currentList.add(candidates[i]);
                result.add(currentList);
                return;
            }
            if(candidates[i] > target){
                return;
            }
            if(candidates[i] < target){
                List<Integer> temp = new ArrayList<Integer>(currentList);
                temp.add(candidates[i]);
                combinationSum2(candidates, target-candidates[i], i+1, temp);
            }
            //去除自遍历中的重复情况
            while(i<candidates.length-1 && candidates[i] == candidates[i+1]){i++;}
        }
    }
    
}