40. 组合总和 II

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

成都创新互联公司成立与2013年，先为赤城等服务建站，赤城等地企业，进行企业商务咨询服务。为赤城企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

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. 组合总和)
重点在于去重：（具体原理见：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>combinationSum2(int[] candidates, int target) {List>combinations = new ArrayList<>();
		Listcombination = 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>combinations, Listcombination, 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;
	}
}

运行结果：

注：仅供学习参考!

来源：力扣.

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：40.组合总和II-创新互联
文章分享：http://hbruida.cn/article/hjspi.html