Problem 1: Combination Sum

Given an array of distinct integers candidates and a target integer target, find all unique combinations where the chosen numbers sum to target. Each number may be used unlimited times.

Algorithm Approach:

The solution uses backtracking with a key condition: when exploring further elements, we start from the current index to allow reuse of elements. The recursion terminates when the acumulated sum exceeds or equals the target.

Implementation:

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<Integer> currentPath = new ArrayList<>();
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0);
        return result;
    }

    private void backtrack(int[] nums, int remaining, int startIndex) {
        int total = calculateSum(currentPath);
        
        if (total > remaining) return;
        if (total == remaining) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        
        for (int i = startIndex; i < nums.length; i++) {
            currentPath.add(nums[i]);
            backtrack(nums, remaining, i); // Pass same index to allow reuse
            currentPath.remove(currentPath.size() - 1);
        }
    }

    private int calculateSum(List<Integer> list) {
        int sum = 0;
        for (int num : list) {
            sum += num;
        }
        return sum;
    }
}

Problem 2: Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in each combination.

Algorithm Approach:

Since duplicates exist in the input, we must avoid duplicate combinations. First, sort the array sothat identical elements are adjacent. Then, during backtracking, skip elements that are the same as their previous element if the previous one hasn't been used yet.

Implementation:

import java.util.*;

class Solution {
    private List<Integer> currentPath = new ArrayList<>();
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtrack(candidates, target, 0, used);
        return result;
    }

    private void backtrack(int[] nums, int remaining, int startIndex, boolean[] used) {
        int total = calculateSum(currentPath);
        
        if (total > remaining) return;
        if (total == remaining) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        
        for (int i = startIndex; i < nums.length; i++) {
            // Skip duplicates
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            
            currentPath.add(nums[i]);
            used[i] = true;
            backtrack(nums, remaining, i + 1, used);
            used[i] = false;
            currentPath.remove(currentPath.size() - 1);
        }
    }

    private int calculateSum(List<Integer> list) {
        int sum = 0;
        for (int num : list) {
            sum += num;
        }
        return sum;
    }
}

Problem 3: Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Algorithm Approach:

Use backtracking to explore all valid partitions. At each step, check if the substring from start index to current index forms a palindrome. If yes, proceed recursively with the next part of the string.

Implementation:

import java.util.*;

class Solution {
    private List<List<String>> partitions = new ArrayList<>();
    private List<String> currentPartition = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return partitions;
    }

    private void backtrack(String str, int startIndex) {
        if (startIndex >= str.length()) {
            partitions.add(new ArrayList<>(currentPartition));
            return;
        }
        
        for (int i = startIndex; i < str.length(); i++) {
            if (isPalindrome(str, startIndex, i)) {
                currentPartition.add(str.substring(startIndex, i + 1));
                backtrack(str, i + 1);
                currentPartition.remove(currentPartition.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}