40. 组合总和 II

柔情只为你懂 2024-03-30 11:55 72阅读 0赞

### 40. 组合总和 II ###

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

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

注意：解集不能包含重复的组合。

##### 示例 1: #####

> 输入: candidates = \[10,1,2,7,6,1,5\], target = 8,  
> 输出:  
> \[  
> \[1,1,6\],  
> \[1,2,5\],  
> \[1,7\],  
> \[2,6\]  
> \]

##### 示例 2: #####

> 输入: candidates = \[2,5,2,1,2\], target = 5,  
> 输出:  
> \[  
> \[1,2,2\],  
> \[5\]  
> \]

##### 提示: #####

1 <= candidates.length <= 100  
1 <= candidates\[i\] <= 50  
1 <= target <= 30

#### 思路（回溯） ####

回溯：（见:[39. 组合总和][39.])  
重点在于去重：（具体原理见：[47. 全排列 II][47. _ II]）

if(i > 0 && candidates[i - 1] == candidates[i] && hasVisited[i - 1] == false) {
    	continue;
    }

#### 代码：（Java） ####

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class combinationSumII {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int [] candidates = {
        10,1,2,7,6,1,5};
    		int target = 8;
    		System.out.println(combinationSum2(candidates, target));
    	}
    	public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
    		List<List<Integer>> combinations = new ArrayList<>();
    		List<Integer> combination = new ArrayList<>();
    		Arrays.sort(candidates);
    		boolean [] hasVisited = new boolean[candidates.length];
    		if(candidates == null || candidates.length == 0){
        
    			return combinations;
    		}
    		backtracking(combinations, combination, candidates, 0 ,target, hasVisited);
    		return combinations;
        }
    	private static void backtracking(List<List<Integer>> combinations, List<Integer> combination, int[] candidates,
    			int start, int target, boolean[] hasVisited) {
        
    		// TODO Auto-generated method stub
    		if(target == 0) {
        
    			combinations.add(new ArrayList<>(combination));
    			return;
    		}
    		int end = search(candidates, target);
    		if(end < start || target < candidates[start]){
        
    			return;
    		}
    		for(int i = start; i <= end; i++){
        
    			if(i > 0 && candidates[i - 1] == candidates[i] && hasVisited[i - 1] == false) {
        
    				continue;
    			}
    			hasVisited[i] = true;
    			combination.add(candidates[i]);
    			backtracking(combinations, combination, candidates, i + 1, target - candidates[i], hasVisited);
    			combination.remove(combination.size() - 1);//回溯
    			hasVisited[i] = false;
    		}
    	}
    	private static int search(int[] candidates, int target) {
        //二分查找
    		// TODO Auto-generated method stub
    		if(target < candidates[0]){
        
    			return -1;
    		}
    		int r = candidates.length - 1;
    		int l = 0;
    		while(l < r) {
        
    			int mid = l + (r - l) / 2;
    			if(candidates[mid] > target) {
        
    				r = mid - 1;
    			}else if(r == l + 1) {
        
    				break;
    			}else{
        
    				l = mid;
    			}
    		}
    		if(candidates[r] > target) {
        
    			r = l;
    		}
    		return r;
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][8340dd6954bf4bb2b0a1b7ef90ccc0c5.png]

###### 注：仅供学习参考! ######

来源：[力扣.][.]

[39.]: https://blog.csdn.net/weixin_43412762/article/details/128204622
[47. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128172523
[8340dd6954bf4bb2b0a1b7ef90ccc0c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/433581c688ea46b99e94ff71bb7a7f63.png
[.]: https://leetcode.cn/problems/combination-sum-ii/description/