flag

软件学院大三党，每天一道算法题，第24天

题目介绍

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

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

说明：

所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-ii

思路

采用回溯法： 先将candidate从小到大排序，然后从左到右依次取一个数字到list中，此时target的值变小， 当target为正数的时候，继续将candidate的下一个数字加入list 当target变成负数的时候，进行回溯。还原list和candidate。 当target为0的时候，说明此时list数组中和正好为target，将该解保存。

关键代码

public class Solution { List<List<Integer>> result; public Solution(){ result=new ArrayList<>(); } public List<List<Integer>> combinationSum2(int[] candidates, int target) { if (candidates == null || candidates.length == 0 || target < 0) { return result; } Arrays.sort(candidates);//数组排序 List<Integer>list=new ArrayList<>(); calculate(0,candidates,target,list); return result; } public void calculate(int start,int []candidates,int target,List<Integer> list){ if(target<0) return; if(target==0) result.add(new ArrayList<>(list)); else { for (int i = start; i < candidates.length; i++) { //因为这个数和上个数相同，所以从这个数开始的所以情况，在上个数里面都考虑过了，需要跳过 if (i > start && candidates[i] == candidates[i - 1]) { continue; } list.add(candidates[i]); calculate(i+1,candidates,target-candidates[i],list); list.remove(list.size() - 1);//回溯 } } } }