https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); backtrack(candidates, target, 0, new ArrayList<>(), res); return res; } private void backtrack(int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> res){ if(remain == 0){ res.add(new ArrayList<>(path)); return; } for(int i = start; i < candidates.length; i++){ // Big Pruning if(candidates[i] > remain){ break; } // Small Pruning if(i > start && candidates[i] == candidates[i - 1]){ continue; } path.add(candidates[i]); backtrack(candidates, remain - candidates[i], i + 1, path, res); path.remove(path.size() - 1); } } }
