712210. Combination Sum II
Medium
Combination Sum II
Slug: combination-sum-ii
Difficulty: Medium
Id: 712210
Topic Tags: None
Company Tags: None
Summary
The Combination Sum II problem involves finding all possible combinations of a given array that sum up to a target value, without considering the order of elements. This problem requires a combination of recursion and dynamic programming to solve efficiently.
Detailed Explanation
To solve this problem, we can use a recursive approach with memoization to keep track of already computed combinations. The basic idea is to iterate through the input array, selecting each element as many times as it appears in the array (since duplicates are allowed), and recursively generate all possible combinations that sum up to the target value.
Here's a step-by-step breakdown of the solution:
- Initialize an empty list
resultto store the final combinations. - Define a recursive function
combinationSum2that takes three parameters:nums,target, andstart.startrepresents the starting index for the current recursion level. - Iterate through the input array
numsfrom thestartindex to its end. - For each element at the current index, recursively call
combinationSum2with the updatedstartindex (i.e.,i + 1) and the remaining target value (target - nums[i]). This will generate all possible combinations that sum up to the reduced target value. - If the recursive function returns a non-empty list of combinations, add it to the
resultlist. - Return the
resultlist containing all possible combinations that sum up to the original target value.
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<>();
combinationSum2Helper(result, new ArrayList<>(), nums, target, 0);
return result;
}
private void combinationSum2Helper(List<List<Integer>> result, List<Integer> tempList, int[] nums, int remain, int start) {
if (remain < 0) return;
else if (remain == 0) result.add(new ArrayList<>(tempList));
else for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
if (nums[i] > remain) break;
tempList.add(nums[i]);
combinationSum2Helper(result, tempList, nums, remain - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}