Combination Sum

LeetCode Q 39 - Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.

Note:

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

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

Solution : Backtracking

Code:

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

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