题目
给定一个数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
代码
public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); dfs(candidates, 0, target, new ArrayDeque<>(), res); return res; } private void dfs(int[] candidates, int pos, int target, Deque<Integer> deque, List<List<Integer>> res) { if (target == 0) { res.add(new ArrayList<>(deque)); } for (int i = pos; i < candidates.length; i++) { if (target - candidates[i] < 0) { break; } /** * 确保 candidates 中每个数字在每个组合中只能使用一次 * candidates[i]==candidates[i-1] 保证在遇到数组中相同元素时跳过 * i>pos 保证是同一层级 */ if (i > pos && candidates[i] == candidates[i - 1]) { continue; } deque.addLast(candidates[i]); dfs(candidates, i + 1, target - candidates[i], deque, res); deque.removeLast(); } }