040 Combination Sum II 组合总和 II

给定候选号码数组 (C) 和目标总和数 (T)，找出 C 中候选号码总和为 T 的所有唯一组合。
C 中的每个数字只能在组合中使用一次。
注意:
所有数字（包括目标）都是正整数。
解决方案集不能包含重复的组合。
例如，给定候选集合 [10, 1, 2, 7, 6, 1, 5] 和目标总和数 8，
可行的集合是：
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
详见：https://leetcode.com/problems/combination-sum-ii/description/

Java实现：

class Solution {

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

        List<List<Integer>> res=new ArrayList<List<Integer>>();

        List<Integer> out=new ArrayList<Integer>();

        Arrays.sort(candidates);

        helper(candidates,target,0,out,res);

        return res;

    }

    private void helper(int[] candidates, int target,int start,List<Integer> out,List<List<Integer>> res){

        if(target<0){

            return;

        }

        if(target==0){

            res.add(new ArrayList<Integer>(out));

        }else{

            for(int i=start;i<candidates.length;++i){

                if(i>start&&candidates[i]==candidates[i-1]){

                    continue;

                }

                out.add(candidates[i]);

                helper(candidates,target-candidates[i],i+1,out,res);

                out.remove(out.size()-1);

            }

        }

    }

}

参考：http://www.cnblogs.com/grandyang/p/4419386.html

巴特西

040 Combination Sum II 组合总和 II

最新文章

热门文章