DSA 450 Notes

Problem Statement

Given an array of distinct integers candidates and a target integer, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen unlimited times. The combinations should be returned in sorted order.

Example:

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

Explanation:
2 + 2 + 3 = 7
7 = 7

Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Approach 1: Brute Force (Generate All Combinations)

Intuition

For each candidate, we have two choices: include it (can be included multiple times) or move to the next candidate. Use recursion to explore all combinations.

Algorithm

Sort candidates for consistent ordering
For each candidate, try including it if it doesn't exceed target
Recurse with reduced target (same index since repeats allowed)
Also try skipping to next candidate
When target becomes 0, store the combination

java

import java.util.*;

class Solution {
    public void backtrack(int[] candidates, int target, int index,
                          List<Integer> current, List<List<Integer>> result) {
        // Found valid combination
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // Base case: exceeded target or no more candidates
        if (target < 0 || index >= candidates.length) {
            return;
        }
        
        // Include current candidate (can repeat)
        current.add(candidates[index]);
        backtrack(candidates, target - candidates[index], index, current, result);
        current.remove(current.size() - 1);
        
        // Skip current candidate
        backtrack(candidates, target, index + 1, current, result);
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, current, result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(2^t) where t = target/min(candidates)
Space Complexity: O(t) - Maximum recursion depth

Approach 2: Optimal (With Pruning)

Intuition

Since array is sorted, once a candidate exceeds the remaining target, we can skip all larger candidates. This prunes the search space significantly.

Algorithm

Sort candidates
In the loop, break early if candidate > target
This avoids exploring branches that will definitely fail

java

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int target, int start,
                           List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            // Pruning: if current candidate > target, skip rest
            if (candidates[i] > target) break;
            
            current.add(candidates[i]);
            // Pass i (not i+1) since we can reuse same element
            backtrack(candidates, target - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
}

Complexity Analysis

Time Complexity: O(2^t) - Still exponential but with pruning
Space Complexity: O(t) - Maximum recursion depth

Combination Sum II (No Repetition)

Problem Variant

Each number can only be used once. Array may contain duplicates.

java

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int target, int start,
                           List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            // Skip duplicates at same level
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            
            if (candidates[i] > target) break;
            
            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

Key Takeaways

Unlimited vs Single Use: Pass same index for repeat, i+1 for single use
Duplicate Handling: Sort and skip consecutive duplicates at same level
Pruning: Break early when candidate exceeds remaining target
LeetCode #39: Combination Sum (with repetition)
LeetCode #40: Combination Sum II (without repetition)
Sorting: Enables both pruning and duplicate handling

Combinational Sum

Problem Statement

Approach 1: Brute Force (Generate All Combinations)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (With Pruning)

Intuition

Algorithm

Complexity Analysis

Combination Sum II (No Repetition)

Problem Variant

Key Takeaways