Skip to content
AI360Xpert
Back to Backtracking
Medium

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 sum to `target`. Each number in `candidates` may only be used once in the combination. Note: The solution set must not contain duplicate combinations.

Examples

Input:candidates = [10,1,2,7,6,1,5], target = 8
Output:[[1,1,6],[1,2,5],[1,7],[2,6]]
Note that the input has two 1s, but each combination that uses two 1s is unique from other combinations.
Input:candidates = [2,5,2,1,2], target = 5
Output:[[1,2,2],[5]]
Valid combinations summing to 5. Duplicates are handled.

Constraints

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Backtracking with Sorting

Approach

Similar to Subsets II, we sort the array first to handle duplicate elements easily. In the backtracking function, we iterate through the remaining candidates. If the current candidate is identical to the previous one at the same level of the decision tree (`i > index`), we skip it to prevent duplicate combinations. Since each number can only be used once, we increment the index by 1 for the recursive call.

Complexity Analysis

Time Complexity
O(2^n)
Space Complexity
O(n)

In the worst case, we might still explore a large number of combinations. The time complexity is O(2^n) and the space complexity is O(n) for the recursion depth.

Solution.java
class Solution {    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        List<List<Integer>> result = new ArrayList<>();        // Sort to handle duplicates        Arrays.sort(candidates);        backtrack(0, candidates, target, new ArrayList<>(), result);        return result;    }        private void backtrack(int index, int[] candidates, int target, List<Integer> current, List<List<Integer>> result) {        // Base case: exact sum found        if (target == 0) {            result.add(new ArrayList<>(current));            return;        }                // Base case: target exceeded (since array is sorted, subsequent elements will also exceed)        if (target < 0) {            return;        }                for (int i = index; i < candidates.length; i++) {            // Skip duplicates at the same level            if (i > index && candidates[i] == candidates[i - 1]) {                continue;            }                        // Optimization: stop if the current element already exceeds the target            if (candidates[i] > target) {                break;            }                        current.add(candidates[i]);            // Recurse with i + 1 because each number can only be used once            backtrack(i + 1, candidates, target - candidates[i], current, result);            current.remove(current.size() - 1);        }    }}