712223. Combination Sum II
Combination Sum II
Summary
Given a set of integers, find all unique combinations that sum up to a given target value. This problem is an extension of the classic "combination sum" problem, where the constraint is added that each combination should be in sorted order.
The key concepts involved are arrays, recursion, and backtracking.
Detailed Explanation
We can solve this problem by using a recursive approach with backtracking. The basic idea is to start from the smallest number and try to add it to the current combination until we reach the target sum. If adding the current number exceeds the target sum, we backtrack and move on to the next smaller number.
Here's a step-by-step breakdown of the solution:
- Initialize an empty list
resultto store all unique combinations. - Define a recursive function
findCombinationsthat takes three parameters:nums,target, andstart.numsis the set of integers,targetis the target sum, andstartis the starting index for the current combination. - In the
findCombinationsfunction:- If the current sum exceeds the target sum, return immediately to backtrack.
- Iterate through the numbers from
startto the end of the array. - For each number, try adding it to the current combination and recursively call
findCombinationswith the updated sum and starting index. - If the recursive call returns a valid combination, add it to the result list.
- Finally, return the result list.
Time complexity: O(N * 2^N), where N is the length of the input array. This is because in the worst case, we might have to explore all possible combinations.
Space complexity: O(N), for storing the result list and recursive call stack.
Optimized Solutions
Java
import java.util.*;
public class CombinationSumII {
public List<List<Integer>> combinationSum2(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
findCombinations(nums, target, 0, new ArrayList<>(), result);
return result;
}
private void findCombinations(int[] nums, int target, int start, List<Integer> combination, List<List<Integer>> result) {
if (target < 0) return;
if (target == 0) result.add(new ArrayList<>(combination));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) continue;
combination.add(nums[i]);
findCombinations(nums, target - nums[i], i + 1, combination, result);
combination.remove(combination.size() - 1);
}
}
}