https://leetcode.wang/leetCode-40-Combination-Sum-II.html
描述
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates 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.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
解析
回溯法
和上一道题非常像了,区别在于这里给的数组中有重复的数字,每个数字只能使用一次,然后同样是给出所有和等于 target 的情况。
代码
回溯法
public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>(); getAnswer(ans, new ArrayList<>(), candidates, target, 0); /*************修改的地方*******************/ // 如果是 Input: candidates = [2,5,2,1,2], target = 5, // 输出会出现 [2 2 1] [2 1 2] 这样的情况,所以要去重 return removeDuplicate(ans); /****************************************/ } private void getAnswer(List<List<Integer>> ans, ArrayList<Integer> temp, int[] candidates, int target, int start) { if (target == 0) { ans.add(new ArrayList<Integer>(temp)); } else if (target < 0) { return; } else { for (int i = start; i < candidates.length; i++) { temp.add(candidates[i]); /*************修改的地方*******************/ //i -> i + 1 ,因为每个数字只能用一次,所以下次遍历的时候不从自己开始 getAnswer(ans, temp, candidates, target - candidates[i], i + 1); /****************************************/ temp.remove(temp.size() - 1); } } } private List<List<Integer>> removeDuplicate(List<List<Integer>> list) { Map<String, String> ans = new HashMap<String, String>(); for (int i = 0; i < list.size(); i++) { List<Integer> l = list.get(i); Collections.sort(l); String key = ""; for (int j = 0; j < l.size() - 1; j++) { key = key + l.get(j) + ","; } key = key + l.get(l.size() - 1); ans.put(key, ""); } List<List<Integer>> ans_list = new ArrayList<List<Integer>>(); for (String k : ans.keySet()) { String[] l = k.split(","); List<Integer> temp = new ArrayList<Integer>(); for (int i = 0; i < l.length; i++) { int c = Integer.parseInt(l[i]); temp.add(c); } ans_list.add(temp); } return ans_list; }
先排序回溯法
public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>(); Arrays.sort(candidates); //排序 getAnswer(ans, new ArrayList<>(), candidates, target, 0); return ans; } private void getAnswer(List<List<Integer>> ans, ArrayList<Integer> temp, int[] candidates, int target, int start) { if (target == 0) { ans.add(new ArrayList<Integer>(temp)); } else if (target < 0) { return; } else { for (int i = start; i < candidates.length; i++) { //跳过重复的数字 if(i > start && candidates[i] == candidates[i-1]) continue; temp.add(candidates[i]); /*************修改的地方*******************/ //i -> i + 1 ,因为每个数字只能用一次,所以下次遍历的时候不从自己开始 getAnswer(ans, temp, candidates, target - candidates[i], i + 1); /****************************************/ temp.remove(temp.size() - 1); } } }