leetcode:40. 组合总和 II

客官°小女子只卖身不卖艺 2022-04-13 02:23 213阅读 0赞

题目连接:  
[https://leetcode-cn.com/problems/combination-sum-ii/description/][https_leetcode-cn.com_problems_combination-sum-ii_description]

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。  
解集不能包含重复的组合。

示例 1:
    
    输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]
    示例 2:
    
    输入: candidates = [2,5,2,1,2], target = 5,
    所求解集为:
    [
      [1,2,2],
      [5]
    ]

使用DFS算法计算,但是发现会出现重复,采用hashset去重,效率很低,待日后优化  
2018年11月26日18:29:08

class Solution {
    	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    		Set<List<Integer>> res = new HashSet<List<Integer>>();
    		List<Integer> temp = new ArrayList<Integer>();
    		// 排序
    		Arrays.sort(candidates);
    		dfs(res, temp, candidates, target, 0);
    		List<List<Integer>> r = new ArrayList<List<Integer>>();
    		r.addAll(res);
    		return r;
    	}
    
    	private void dfs(Set<List<Integer>> res, List<Integer> temp, int[] candidates, int target, int start) {
    
    		if (target == 0) {
    			List<Integer> list = new ArrayList<Integer>();
    			list.addAll(temp);
    			res.add(list);
    			return;
    		}
    
    		for (int i = start; i < candidates.length && candidates[i] <= target; i++) {
    			temp.add(candidates[i]);
    			dfs(res, temp, candidates, target -candidates[i], i + 1);
    			temp.remove(temp.size() - 1);
    		}
    
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_combination-sum-ii_description]: https://leetcode-cn.com/problems/combination-sum-ii/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220413/5ad8e575cbf248c5b2f5c6aef76ed28c.png