Java - Program - Sum to a Target(Combination Sum II)

 

Programing — Sum to a Target(Combination Sum II)

Combination Sum II is a classic backtracking problem where you find all unique combinations of numbers that sum to a target, using each number at most once.

🎯 Problem Statement

Given a list of integers candidates and an integer target, return all unique combinations of candidates where the chosen numbers sum to target.
Each number in candidates may be used only once in the combination.

📌 Constraints

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• 1 ≤ target ≤ 30
• The solution set must not contain duplicate combinations

🧠 Key Strategy: Backtracking with Pruning

1. Sort the array to handle duplicates.
2. Use backtracking to explore combinations.
3. Skip duplicates at the same recursive level.


4. Track used elements to avoid reusing the same index.

✅ Java Code Example

import java.util.*;

public class CombinationSumII {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);  // Sort to handle duplicates
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }    private void backtrack(int[] candidates, int target, int start, List<Integer> tempList, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(tempList));
            return;
        }        for (int i = start; i < candidates.length; i++) {
            // Skip duplicates
            if (i > start && candidates[i] == candidates[i - 1]) continue;            if (candidates[i] > target) break;            tempList.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, tempList, result);
            tempList.remove(tempList.size() - 1);
        }
    }    public static void main(String[] args) {
        CombinationSumII cs = new CombinationSumII();
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> combinations = cs.combinationSum2(candidates, target);
        System.out.println(combinations);
    }
}

🧾 Sample Output

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

🔍 Real-World Analogy

Think of this like selecting items from a shopping list where each item can be picked only once, and your goal is to match a budget exactly — but you want all possible unique ways to do it.