Combination Sum I, II, II, IV

39,40,216,377.Combination Sum Solutions

Array

Backtracking

Recursion

Dynamic Programming

Problem Statements:

I: Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may reuse elements.
II: Same as I but each number may only be used once.
III: Find all valid combinations of k numbers that sum up to n, using numbers 1-9 only once.
IV: Given array of distinct integers, return number of possible combinations that add up to target. Order matters.

Java Solutions:

// Combination Sum I: Can reuse elements
class Solution {
    public ListInteger>> combinationSum(int[] nums, int target) {
        ListInteger>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums, target, 0);
        return list;
    }

    private void backtrack(ListInteger>> list, List<Integer> tempList, 
            int[] nums, int remain, int start) {
        if(remain < 0) return;
        else if(remain == 0) list.add(new ArrayList<>(tempList));
        else{ 
            for(int i = start; i < nums.length; i++){
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i); // i allows reuse
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

// Combination Sum II: Cannot reuse elements, need to skip duplicates
class Solution {
    public ListInteger>> combinationSum2(int[] nums, int target) {
        Arrays.sort(nums); // Sort to handle duplicates
        ListInteger>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums, target, 0);
        return list;
    }

    private void backtrack(ListInteger>> list, List<Integer> tempList, 
            int[] nums, int remain, int start) {
        if(remain < 0) return;
        else if(remain == 0) list.add(new ArrayList<>(tempList));
        else{
            for(int i = start; i < nums.length; i++){
                if(i > start && nums[i] == nums[i-1]) continue; // Skip duplicates
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i + 1); // i+1 prevents reuse
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

// Combination Sum III: k numbers that sum to n using 1-9
class Solution {
    public ListInteger>> combinationSum3(int k, int n) {
        ListInteger>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), k, n, 1);
        return list;
    }

    private void backtrack(ListInteger>> list, List<Integer> tempList, 
            int k, int remain, int start) {
        if(tempList.size() > k) return; // Check k numbers constraint
        if(remain < 0) return;
        else if(remain == 0 && tempList.size() == k) list.add(new ArrayList<>(tempList));
        else{
            for(int i = start; i <= 9; i++){ // Only numbers 1-9
                tempList.add(i);
                backtrack(list, tempList, k, remain - i, i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

// Combination Sum IV: Order matters (DP solution)
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1; // Base case: one way to make sum 0
        
        for(int i = 1; i <= target; i++){
            for(int num : nums){
                if(i >= num){
                    dp[i] += dp[i - num]; // Add all possible combinations
                }
            }
        }
        return dp[target];
    }
}

Key Differences:

1. I: Can reuse elements (use i as start)
2. II: No reuse, must skip duplicates (use i+1, need sorting)
3. III: Fixed k size, numbers 1-9 only (check size, limit range)
4. IV: Order matters (uses DP instead of backtracking)

Complexity:

I, II, III: Time: O(2^n) | Space: O(n)
IV: Time: O(target * n) | Space: O(target)