40. 组合总和 II

1. 此题和 39. 组合总和 + 递归 + 回溯 + 存储路径很像，只不过题目修改了一下。

2. 题解的关键是首先将候选数组进行排序，然后记录每个数的出现次数。

3. 将去重后的数组当成是新的候选数组进行递归搜索。

4. 回溯的时候注意是在最后将相同数字次数的数从列表中清除。

   package com.walegarrett.interview;

   import java.util.ArrayList;
   import java.util.Arrays;
   import java.util.List;

   /**

   • @Author WaleGarrett
   • @Date 2021/2/27 17:53
     */

   /**

   • 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
   • candidates 中的每个数字在每个组合中只能使用一次。
     */

   /**

   • 解法：回溯法
     / public class LeetCode_40 { public List> combinationSum2(int[] candidates, int target) { List> result = new ArrayList<>(); List list = new ArrayList<>(); List map = new ArrayList<>(); Arrays.sort(candidates); for(int num : candidates){ if(map.isEmpty() || num != map.get(map.size()-1)[0]) map.add(new int[]{num, 1}); else{ ++map.get(map.size()-1)[1]; } } dfs(target, 0, list, result, map); return result; } public void dfs(int target, int index, List path, List> result, List map){ //找到一条路径 if(target == 0){ //注意：这里不能直接result.add(path)，因为path是在回溯中会改变的，这样只存储了list的地址，地址是不变的。 result.add(new ArrayList<>(path)); return; } if(index == map.size() || target < map.get(index)[0]) return; //跳过当前数 dfs(target, index+1, path, result, map); //不跳过当前数 int ans = Math.min(map.get(index)[1], target/map.get(index)[0]); for(int i=1; i<=ans; i++){ path.add(map.get(index)[0]); dfs(target- imap.get(index)[0], index+1, path, result, map);
     }
     for(int i=1; i<=ans; i++){
     path.remove(path.size()-1);
     }
     }
     }