题目
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
思路
根据给定数组可以想象构成一父节点的子节点为数组全部元素的树,然后利用深度优先遍历和回溯剪枝。
代码
public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); dfs(candidates, 0, target, new ArrayDeque<>(), res); return res; } private void dfs(int[] candidates, int i, int target, Deque<Integer> deque, List<List<Integer>> res) { if (target < 0) { return; } if (target == 0) { res.add(new ArrayList<>(deque)); return; } for (int j = i; j < candidates.length; j++) { deque.addLast(candidates[j]); dfs(candidates, j, target - candidates[j], deque, res); deque.removeLast(); } }
优化
排序后加快剪枝
public List<List<Integer>> combinationSum(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 i, int target, Deque<Integer> deque, List<List<Integer>> res) { if (target == 0) { res.add(new ArrayList<>(deque)); return; } for (int j = i; j < candidates.length; j++) { if (target - candidates[j] < 0) { // 如果当前节点的和已经大于 target,后面的就可以直接剪枝 break; } deque.addLast(candidates[j]); dfs(candidates, j, target - candidates[j], deque, res); deque.removeLast(); } }