40. 组合总和 II
发布时间:2020-12-14 04:46:50 所属栏目:大数据 来源:网络整理
导读:题目描述 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明: 所有数字(包括目标数)都是正整数。 解集不能包含重复的组合。 示例 1: 输入:
题目描述给定一个数组
说明:
示例 1: 输入: candidates = [10,1,2,7,6,5],target = 8,所求解集为: [ [1,7],[1,[2,6],6] ] 示例 2: 输入: candidates = [2,5,2],target = 5,[5] ] 分析(DFS枚举)
贴出代码class Solution { public List<List<Integer>> combinationSum2(int[] candidates,int target) { List<List<Integer>> res = new ArrayList<>(); if (candidates == null || candidates.length == 0 || target <= 0){ return res; } Arrays.sort(candidates); dfs(res,new ArrayList<>(),candidates,target,0); return res; } private void dfs(List<List<Integer>> res,List<Integer> temp,int[] candidates,int remind,int start){ if (remind < 0){ return; } if (remind == 0){ res.add(temp); return; } for (int i = start; i < candidates.length; i ++){ if (i > start && candidates[i] == candidates[i - 1]){ continue; } temp.add(candidates[i]); dfs(res,new ArrayList<>(temp),remind - candidates[i],i + 1); temp.remove(temp.size() - 1); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |