【Leetcode 每日一题】40. 组合总和 II

问题背景

给定一个候选人编号的集合 $candidates$ 和一个目标数 $target$，找出 $candidates$ 中所有可以使数字和为 $target$ 的组合。
$candidates$ 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

数据约束

• $1\le candidates.length\le 100$
• $1\le candidates[i]\le 50$
• $1\le target\le 30$

解题过程

算是回溯的例题，由于结果不能重复，要先将数组进行排序，方便在过程中跳已经处理过的相等元素。

具体实现

递归

class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(0, target, candidates, res, path);return res;}private void dfs(int i, int target, int[] candidates, List<List<Integer>> res, List<Integer> path) {if(target == 0) {res.add(new ArrayList(path));return;}if(i == candidates.length) {return;}int cur = candidates[i];if(target < cur) {return;}path.add(cur);dfs(i + 1, target - cur, candidates, res, path);path.remove(path.size() - 1);i++;while(i < candidates.length && candidates[i] == cur) {i++;}dfs(i, target, candidates, res, path);}
}

递推

class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(0, target, candidates, res, path);return res;}private void dfs(int i, int target, int[] candidates, List<List<Integer>> res, List<Integer> path) {if(target == 0) {res.add(new ArrayList<>(path));return;}for (int j = i; j < candidates.length && candidates[j] <= target; j++) {if(j > i && candidates[j] == candidates[j - 1]) {continue;}path.add(candidates[j]);dfs(j + 1, target - candidates[j], candidates, res, path);path.remove(path.size() - 1);}}
}