40. Combination Sum II

发表于 | 分类于 | 阅读次数
字数统计 558 | 阅读时长 3

40. Combination Sum II

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]
]

题意：

　　题意同39. Combination Sum,不同点就是，给定的数组元素含有重复元素值,而且每个元素在组合数组中只能出现一次。

思路：

　　思路同39. Combination Sum,不同点就是，因为数组元素含有重复元素值，所以再递归的过程中，要进行判断，跳过重复元素。

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
class Solution {

public:
	vector<vector<int>> res;
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<int> sumNum;
		sort(candidates.begin(), candidates.end());
		backtracking(candidates, target, 0, 0, sumNum);
		return res;
	}
	void backtracking(vector<int> candidates, int target, int index, int sum, vector<int> sumNum) {
		if (sum == target)
		{
			res.push_back(sumNum);
			return;
		}
		else
		{
			for (int i = index; i < candidates.size(); i++)
			{
				if (sum + candidates[i] > target)//已经排序，可以剪枝
				{
					break;
				}
				if (i==index||candidates[i]!=candidates[i-1])//此处剪枝去除重复的元素，index是控制同一层元素，当i!=index得时候，肯定是同一层往后找同层元素，此时进行判断是否相等可以把重复元素去掉，因为已经排过序了
				{
					sumNum.push_back(candidates[i]);
					backtracking(candidates, target, i + 1, sum + candidates[i], sumNum);//此处索引i + 1取下一个元素，防止数组中一个元素取多次
					sumNum.pop_back();
				}

			}
		}
	}
};

　Java Code：

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
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (null == candidates) {
            return new ArrayList();
        }
        int len = candidates.length;
        if (len == 0) {
            return new ArrayList();
        }

        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList();
        List<Integer> sumElements = new ArrayList();
        getCombinations(candidates, target, 0, 0, sumElements, res);
        return res;
    }

    public  void  getCombinations(int[] candidates, int target, int index, int sum, List<Integer> sumElements, List<List<Integer>> res){
        if (sum == target) {
            res.add(sumElements);
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if(i != index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (sum + candidates[i] > target) {
                break;
            }
            List<Integer> tmpSumElements = new ArrayList(sumElements);
            tmpSumElements.add(candidates[i]);
            getCombinations(candidates, target, i + 1, sum + candidates[i], tmpSumElements, res);
        }
    }
}