[LeetCode] 40. Combination Sum II

用户1148830

发布于 2018-01-03 17:45:33

5050

发布于 2018-01-03 17:45:33

【原题】 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]
]

【解释】和Combination Sum目标相同，但是给定的候选集合中可能会有重复的元素，而再返回的集合当中要求不能重复。且同一个元素不能重复使用。【思路】主要的问题在于相同元素会导致结果当中有相同的集合，使用排序可以解决重复集合的问题。

public class Solution {
    public void combinationSumCore(List<List<Integer>> results, List<Integer> result,int[] candidates,int index,int target,int sum){
        if(sum==target) {
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.length;i++){
            if(i>index&&candidates[i]==candidates[i-1])//相同的元素跳过，用来避免同一子集多次加入到结果集合当中
             continue;
            result.add(candidates[i]);
            sum+=candidates[i];
            combinationSumCore(results, result,candidates,i+1,target,sum);//元素不能重复使用所以从下一个元素开始
            sum-=candidates[i];
            result.remove(result.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        List<Integer> result=new ArrayList<>();
        Arrays.sort(candidates);//先排序
        combinationSumCore(results,result,candidates,0,target,0);
        return results;
    }
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年06月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

each