✨今日算法一题
由于最近事情变多，每日刷题暂时调整为一题，刷题不一定贪多，但是要刷一题有用一题。
文章目录
组合总和
题目描述
思路详解
本题相对比较难，下面是参考官方解答的自我解释。方法：回溯。
首先我们定义三个成员变量这样递归的时候就不用每次都传入了。
- 我们用dfs(pos,rest) 表示递归的函数，其中pos 表示我们当前递归到了数组 candidates 中的第 \textit{pos}pos 个数，而rest 表示我们还需要选择和为rest 的数放入列表作为一个组合；
- 对于当前的第 pos 个数，我们有两种方法：选或者不选。如果我们选了这个数，那么我们调用dfs(pos+1,rest−candidates[pos]) 进行递归，注意这里必须满足 rest≥candidates[pos]。如果我们不选这个数，那么我们调用 dfs(pos+1,rest) 进行递归；
- 在某次递归开始前，如果rest 的值为 0，说明我们找到了一个和为 target 的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。
为了解决重复的问题，这里采用哈希映射（HashMap）。
- 我们使用一个哈希映射（HashMap）统计数组 candidates 中每个数出现的次数。在统计完成之后，我们将结果放入一个列表 \freq 中，方便后续的递归使用。
- 列表 freq 的长度即为数组 candidates 中不同数的个数。其中的每一项对应着哈希映射中的一个键值对，即某个数以及它出现的次数。
- 在递归时，对于当前的第pos 个数，它的值为 freq[pos][0]，出现的次数为 freq[pos][1]，那么我们可以调用dfs(pos+1,rest−i×freq[pos][0])
- 即我们选择了这个数 i 次。这里 i 不能大于这个数出现的次数，并且 i×freq[pos][0] 也不能大于 rest。同时，我们需要将 i 个 freq[pos][0] 放入列表中。
代码与结果
class Solution { List<int[]> freq = new ArrayList<int[]>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); List<Integer> sequence = new ArrayList<Integer>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); for (int num : candidates) { int size = freq.size(); if (freq.isEmpty() || num != freq.get(size - 1)[0]) { freq.add(new int[]{num, 1}); } else { ++freq.get(size - 1)[1]; } } dfs(0, target); return ans; } public void dfs(int pos, int rest) { if (rest == 0) { ans.add(new ArrayList<Integer>(sequence)); return; } if (pos == freq.size() || rest < freq.get(pos)[0]) { return; } dfs(pos + 1, rest); int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]); for (int i = 1; i <= most; ++i) { sequence.add(freq.get(pos)[0]); dfs(pos + 1, rest - i * freq.get(pos)[0]); } for (int i = 1; i <= most; ++i) { sequence.remove(sequence.size() - 1); } } }
✨总结
深度优先算法比较难懂，也比较重要更加多加练习！
