40. 組合總和 II

給定一個(gè)候選人編號(hào)的集合 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

成都創(chuàng)新互聯(lián)公司成立與2013年，先為赤城等服務(wù)建站，赤城等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為赤城企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用 一次 。

注意：解集不能包含重復(fù)的組合。

示例 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. 組合總和)
重點(diǎn)在于去重：（具體原理見：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;
	}
}

運(yùn)行結(jié)果：

注：僅供學(xué)習(xí)參考!

來(lái)源：力扣.

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：40.組合總和II-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://weahome.cn/article/hjspi.html