今年的就业环境，太差。。。
点击关注 👉约 5 分钟今年的就业环境大家都是心知肚明的，只是能有多差，我还是想看看网友们怎么秀。
一位网友开门见山：“boss直聘在ios下载排行榜上排名第三，这还用问吗？” 有点东西，但不够秀。
另一个网友也不甘示弱：“我把 boss 当抖音刷” 好家伙，高端玩家。
更有位网友张口就来：“以前我吃啥狗吃啥，现在狗吃啥我吃啥！” 整活还得是你。
而大部分网友的回答，都表达了一个意思：“未读、送达、已读不回。” 短短几个字，却砍出了真伤。
看到网友们还能开玩笑，如此乐观的态度，突然就感觉轻松很多了。虽然环境就这样，但是我们还得向前看，加油，你我共勉。
给定一个可能包含重复元素的整数数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
专属福利 👉点击领取：最全Python资料合集
由于不使用回溯算法，我们可以考虑动态规划（Dynamic Programming，DP）作为解决方案。具体的动态规划方法可能在处理重复元素和保证每个数字只使用一次上有所不同，这里介绍一种处理方式：
排序：首先对 candidates 数组进行排序，以方便处理重复元素。
初始化DP表：创建一个列表（或数组）dp，其中 dp[i] 存储所有和为 i 的组合列表。dp[0] 初始化为一个空列表的列表，表示和为0的组合仅有空集。
填充DP表：遍历每个数字，对于每个数字，反向遍历从 target 到该数字的值，更新 dp[i] 的值。这样做可以确保每个数字仅被使用一次。
避免重复组合：在更新 dp[i] 时，如果当前数字与前一个数字相同，则只在上一轮新增的组合基础上添加当前数字，避免产生重复的组合。
Java 实现同样依赖于先对数组进行排序，然后使用递归和剪枝的方式来避免重复组合。
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(candidates); // 排序backtrack(result, new ArrayList<>(), candidates, target, 0);return result;}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {if (remain < 0) return; // 剪枝else if (remain == 0) result.add(new ArrayList<>(tempList)); // 找到一个组合else {for (int i = start; i < candidates.length; i++) {if (i > start && candidates[i] == candidates[i-1]) continue; // 跳过重复元素tempList.add(candidates[i]);backtrack(result, tempList, candidates, remain - candidates[i], i + 1); // 递归tempList.remove(tempList.size() - 1); // 回溯}}}}
function combinationSum2(candidates, target) {let result = [];candidates.sort((a, b) => a - b); // 排序以方便处理重复元素const findCombination = (start, target, path) => {if (target === 0) {result.push([...path]);return;}for (let i = start; i < candidates.length; i++) {if (i > start && candidates[i] === candidates[i-1]) continue; // 跳过重复元素if (candidates[i] > target) break; // 由于数组已排序，后续不会有合法组合findCombination(i + 1, target - candidates[i], [...path, candidates[i]]);}};findCombination(0, target, []);return result;}
Go实现
Go 的实现也需要先排序，然后利用递归来遍历所有可能的组合，同时注意避免重复。
package mainimport ("sort")func combinationSum2(candidates []int, target int) [][]int {sort.Ints(candidates) // 排序result := [][]int{}backtrack(&result, []int{}, candidates, target, 0)return result}func backtrack(result *[][]int, temp []int, candidates []int, remain int, start int) {if remain < 0 {return // 剪枝} else if remain == 0 {comb := make([]int, len(temp))copy(comb, temp)*result = append(*result, comb) // 找到一个组合} else {for i := start; i < len(candidates); i++ {if i > start && candidates[i] == candidates[i-1] {continue // 跳过重复元素}// 递归并回溯backtrack(result, append(temp, candidates[i]), candidates, remain-candidates[i], i+1)}}}
算法解析
示例和测试
输入：candidates = [10,1,2,7,6,1,5], target = 8输出：[[1,1,6],[1,2,5],[1,7],[2,6]]输入：candidates = [2,5,2,1,2], target = 5输出：[[1,2,2],[5]]
热门推荐