Combination Sum II
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Combination Sum II * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Combination Sum II * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an array of size N of candidate numbers A and a target number B. * Return all unique combinations in A where the candidate numbers sum to B. * * Key Constraints: * 1. Usage: Each number in A may only be used ONCE in the combination. * 2. Ordering: Elements in a combination must be in non-descending order. * 3. Uniqueness: The solution set must not contain duplicate combinations. * (e.g., if input is [1, 1] and target is 1, output should be [[1]], not [[1], [1]]). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let F(index, currentSum, path) be a recursive function that builds valid combinations. * * Critical Pre-processing: * Since the input array may contain duplicates and the output must be unique: * 1. SORT the array A. * - This places identical elements adjacent to each other. * - This allows for early termination (pruning) if the current sum exceeds B. * * Recursion Strategy (Backtracking): * Iterate through the array starting from 'index'. For every element A[i]: * * 1. Skip Duplicates: * If A[i] == A[i-1] and i > index: * We skip this element because it would generate a permutation identical to the one * generated by the previous instance of this number (which was already processed). * * 2. Pruning: * If (currentSum + A[i] > B): * Break the loop immediately. Since A is sorted, all subsequent numbers will also be too large. * * 3. Include & Recurse: * - Add A[i] to the path. * - Recurse: F(i + 1, currentSum + A[i], path). * (Note: We pass 'i + 1' because the current element cannot be reused). * - Backtrack: Remove A[i] from path. * * Base Case: * If currentSum == B: Add a deep copy of 'path' to the result list and return. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= N <= 20 * * Time Complexity: * O(2^N) - In the worst case, we explore all subsets. * Sorting takes O(N log N). * The constraints (N <= 20) ensure this approach runs well within time limits. * * Space Complexity: * O(N) - Recursion stack depth. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - Integer Array A. * - Integer B (Target). * * Output: * - A list of lists (ArrayList of ArrayLists) containing unique combinations. * * --------------------- * 5. Examples * --------------------- * Input 1: A = [10, 1, 2, 7, 6, 1, 5], B = 8 * Sorted A: [1, 1, 2, 5, 6, 7, 10] * * Trace (Partial): * - Start with 1 (index 0): Remainder 7. * - Next 1 (index 1): Remainder 6. -> find 6. -> [1, 1, 6] (Valid) * - Next 2 (index 2): Remainder 5. -> find 5. -> [1, 2, 5] (Valid) * - ... * - Start with 1 (index 1): SKIP (Duplicate of index 0). * - Start with 2 (index 2): Remainder 6. -> find 6. -> [2, 6] (Valid) * * Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]] * * ============================================================================================ */ public class CombinationSumII { public int solve(int A) { // TODO: Implement solution return 0; }
public ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> input1, int i) {
return new ArrayList<>();
}
}