Combination Sum II

LeetCode Q 39 - Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

Solution : Backtracking

Code:

private List<List<Integer>> res;
public List<List<Integer>> combinationSum2(int[] cand, int target) {
	res = new ArrayList<>();
	if (cand == null || cand.length == 0) return res;
	Arrays.sort(cand);
	backtrack(cand, target, 0, new ArrayList<>());
	return res;
}

private void backtrack(int[] cand, int target, int index, List<Integer> temp) {
	if (target == 0) {
		res.add(new ArrayList(temp)); return;
	} else if (target < 0) {
		return;
	}
	
	for (int i = index; i < cand.length; i++) {
		if (i != index && cand[i] = cand[i - 1]) continue;
		temp.add(can[i]);
		backtrack(can, target, i, currSum + can[i], temp);
		temp.remove(temp.size() - 1);
	}
}