1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| public class Q40 { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); dfs(candidates, target, 0, new Stack<>(), res); return res; }
private void dfs(int[] candidates, int target, int index, Stack<Integer> temp, List<List<Integer>> res) { if (target == 0) { res.add(new ArrayList<>(temp)); return; } for (int i = index; i < candidates.length; ) { if (candidates[i] > target) { return; } temp.push(candidates[i]); dfs(candidates, target - candidates[i], i + 1, temp, res); temp.pop(); int nextI = i + 1; while (nextI < candidates.length && candidates[nextI] == candidates[i]) { nextI++; } i = nextI; } }
public static void main(String[] args) { new Q40().combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8).forEach(System.out::println); }
}
|